Ahh, I remember having this mind boggling problem. Look at your resolv.conf file. Check that you have correct nameservers in there. If so, then you don't have a PTR record for that host you are trying to connect. Yes, when you read this you would be "uhh, no. My problem is with ssh, not DNS." They are related.

.
Another way to handle this is in your sshd_config, change it to:
UseDNS no
-twantrd