Domains won't map

I added 2 new sites to an MU installation a couple of weeks ago. The nameservers are set, the IP is set, the aliases are set, everything should go, but they won't map. Hosting's tech support went into Network admin>sites>info and changed the site url to newsite.com, instead of mainsite.com/newsite, thinking that would fix it. But it just sent the site to a sort of under construction page. So they changed it back. What would cause these domains to not map?