I have a site at dem.co it is a multi site install that works fine for adding sites under that.
I have installed the multi-domains plugin and added some domains there. I have setup the dns to all point to a dedicated IP 126.96.36.199. All the domains ping there as far as I know.
I can add sites at will on the dem.co domain (which is the actual wordpress install) when I add a site under one of the MS domains, it jumps straight to home on the dem.co site.
DNS background, I was able to install the domain mapping plugin and map domains to sites successfully, using the proper dns techniques. I have removed all mapping functions at Ivan's request so we can try to resolve the issue.