Olá Pessoal!
para mim funcionou batata!!
rodo ubuntu 8.10 e ocorria o mesmo problema, então procurei nos fóruns da vida e nada...
foi quando vi que o serviços wins (que é a forma do windows lidar com o dns) esta off por padrão nos ubuntus mais recentes...
resolvi assim:
como root, edite o arquivo /etc/samba/smb.conf (ex.: sudo gedit /etc/samba/smb.conf)
procure a linha: # wins support = no
descomente (tire o caracter #) e troque o no por yes.
e pronto...
é necessário reiniciar o serviço...
para os menos letrados como eu, deslogue e logue novamente.
relatem os resultados!