Descobri isso!
/etc/resolv.conf tinha isso
nameserver ip-addres # hostname
Eu pensei que o arquivo foi replicado para todos os hosts, mas não foi! Não funciona se você colocar um comentário na linha. Eu suspeito que qualquer linha com um "#" é ignorada, não apenas o texto após o "#"
Tanto para documentação. :)