Edite o arquivo /etc/nsswitch.conf e verifique se "dns" aparece antes de "mdns4" ou "mdns4_minimal" para a linha "hosts".
Por exemplo isto é o que o Ubuntu Desktop parece por padrão:
hosts: files mdns4_minimal [NOTFOUND=return] mdns4 dns
Alterá-lo para isso resolve o problema:
hosts: files dns mdns4_minimal [NOTFOUND=return] mdns4