Is MySQL attempting to do reverse resolution of the hostname of connecting clients' IP addresses? (And do those entries not exist?)
Try adding skip-name-resolve to your MySQL configuration. If you don't need name resolution (no hostnames in the host specification of user accounts) then you may as well have it off.