O problema é que todos os nossos servidores na rede são nomeados * .local e isso é inerentemente incompatível com o Avahi. Mais leitura .
A solução que usei foi editar /etc/nsswitch.conf e mudar a seguinte linha:
hosts: files mdns4_minimal [NOTFOUND=return] dns
Para:
hosts: files dns mdns4_minimal [NOTFOUND=return]