Help me understand this a bit...

[Nicholas Leippe]

Sounds like DNS.

For sshd, in /etc/ssh/sshd_config you can set:

UseDNS no

For MySQL, in the [mysqld] section of your my.cnf you can set:

skip-name-resolve

Be forewarned that this affects any grants for connections based on hostnames.

Or, you can fix your network dns configuration.

For a production MySQL server, I highly recommend disabling dns lookups, and 
do ip-based grants.  Typically, external connections aren't allowed to MySQL 
anyways.