The message *Host ''xxx.xx.xxx.xxx'' is not allowed to connect to this MySQL server is a reply from the MySQL server to the MySQL client. Notice how its returning the IP address and not the hostname.
If you're trying to connect with mysql -h<hostname> -u<somebody> -p and it returns this message with the IP address, then the MySQL server isn't able to do a reverse lookup on the client. This is critical because thats how it maps the MySQL client to the grants.
Make sure you can do an nslookup <mysqlclient> FROM the MySQL server. If that doesn't work, then there's no entry in the DNS server. Alternatively, you can put an entry in the MySQL server's HOSTS file (<ipaddress> <fullyqualifiedhostname> <hostname> <- The order here might matter).
An entry in my server's host file allowing a reverse lookup of the MySQL client solved this very problem.