The OpenSSH server on the server attempts to look up the reverse DNS of the connecting machine. The client machine does not have a host name (i.e. reverse DNS) set up. The quick solution is to edit /etc/nsswitch.conf
...
# Change this line
# hosts: files mdns4_minimal [NOTFOUND=return] dns mdns4
# To this (removed mdns4)
hosts: files mdns4_minimal [NOTFOUND=return] dns