Obfuscurity may be right. First thing I would check is reverse DNS. To troubleshoot this try setting the --skip-name-resolve flag to mysqld:

http://dev.mysql.com/doc/refman/5.0/en/server-options.html#option_mysqld_skip-name-resolve

Also make sure to add your hostname/ip to /etc/hosts


Are you using a hostname or IP address to connect? Sounds like you might be experiencing slow DNS resolution.