Eu consertei o problema sozinho:
Eu tive que adicionar /etc/network/interfaces
uma linha com os servidores de nomes:
dns-nameservers 172.16.194.5 172.16.194.200
Depois de reiniciar a rede com sudo service networking restart
, funcionou.