MySQL Replication via DNS Failure
I feel terrible for forgetting about this question!!!

I have located and fixed the problem as follows.

When the DNS names were added to DNS, the corresponding reverse lookup was not created.

This resulted in MySQL not being able to perform the reverse lookup from the IP address to the correct DNS name, and therefore rejecting the connection.

So, we added a set of reverse lookups from IP address to DNS names, ran FLUSH HOSTS; on all of the MySQL boxes, and everything started working.

We require the use of DNS names for all connections, due to our disaster recovery solution being in a separate data centre, and a virtually identical VM farm, but with the IP addresses of all the machines modified only slightly. If / When we have a complete fail-over to the other data centre, all the software and communications will just "work", as the DNS resolution will always give the correct address based on the data centre.

You just need to be careful not to have TWO (or more) names reverse looking up from the same IP address, as there is no guarantee which of the two names will be returned - sometimes your connection will work, and other times it won't.

Hope this helps someone with the same problem!

Regards,
Dave