É algo que vem errado na instalação do Ubuntu.
Para consertar isso, você precisa mudar esta linha em /etc/nsswitch.conf :
hosts: files mdns4_minimal [NOTFOUND=return] dns mdns4
E altere para este:
hosts: files dns
Quando tento conectar o ssh, demora muito (quase 2 minutos) para aparecer o prompt de senha.
Por que isso acontece?