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: