I had a similar situation on my setup where the database lived on a different host than the webserver. I found the "unauthenticated users" were connections from the webserver that were hanging on DNS lookups. Don't know if this is a mysql bug or a bug with my firewall / other setup, but a couple of fixes I found were... 1) start mysql with --skip-name-resolve (you may have to change your mysql permission tables to have the host's IP instead of hostname, including localhost) or 2) add the connecting host to your /etc/hosts file.
- Kevin Owocki