Invalid Domain on Every Domain We try to Map

We recently setup the domain mapping plugin on our new multi-site Every time we try to map a new domain, we get an error "Domain Name is Invalid". This never happens on our other site ( using the same plugin.

We're also using the Multi-Domain plugin. I also read that we should try parking the domains, but that hasn't worked either. Any guidance would be helpful.