Acontece que apenas instalar o libnss-mdns
não é suficiente, você precisa de alguma configuração para usá-lo.
Particularmente, a linha do host do arquivo /etc/nsswitch.conf
deve ter mdns4
em algum lugar.
Minha linha de host de /etc/nsswitch.conf
para qualquer pessoa que possa ter o mesmo problema:
hosts: files mdns4 [NOTFOUND=return] dns