Eu tive resultados muito bons em ambientes de rede mista (window-ubuntu) com este método:
1) Pressione alt + F2 > > tipo gksu gedit /etc/nsswitch.conf
2) Procure por esta linha: hosts: arquivos mdns4_minimal [NOTFOUND = return] dns mdns4
3) Adicione "wins" para que fique assim: hosts: arquivos mdns4_minimal [NOTFOUND = return] wins dns mdns4
4) Instale o pacote "winbind": sudo apt-get install winbind (ou via software center ou synaptic)
5) Reinicie ou reinicie sua rede