Problem with A records for multi-domain

I have set up multi-domains on my pro sites site which also has domain mapping.
I created what I think are the right A records for wildcard subdomains.
But in the Multi-Domains dashboard I get a warning:

Warning! Wildcard DNS for may not be configured correctly!
Unable to contact the random hostname (

But in my DNS manager, I have
`* IN A'
which is the correct dedicated IP.

I pretended to be a new user and after registering as a new site, I get a message that my browser cannot find the server for that request.

Some of the things I've been thinking about that might be the problem are:

* I added the extra domains as add-on domains to the main site. But I think if I delete them then I might loose my dns records? (I am using WHMCS)

Any pointers, or questions to clarify?