Pode ser mDNS / DNS-SD .
Os sintomas seriam que a resolução de nomes que passa pelo nss / libc falha (ou seja, quando você usa aplicativos como um navegador, ping etc.) mas resolução de nomes com aplicativos que consultam dns diretamente (ou seja, host, dig, etc.) consegue resolver o nome.
Se este for o caso, no Ubuntu você pode tentar alterar a entrada do host no arquivo /etc/nsswitch.conf
(remove mdns4_minimal [NOTFOUND=return]
) para dizer algo como:
hosts: files dns mdns4