Domain Mapping not working for me

Hi there,

I keep getting 'Domain name is unavailable to access' when I try and map domains to my WordPressMU install.

I've been struggling with mapping a new domain for a day or so now, initially I thought it was because of transfers and propagation but, out of interest I unmapped a domain that was working and tried to remap it and I get the same message, even though the domain I was testing showed as healthy 5 minutes before.