Comment 13 for bug 235560

I had the 100% exact same problem that Andy describes. However, for me it was not a problem with Nautilus at all, and just a misconfiguration of samba's name resolution.

The way I fixed it was
sudo gedit /etc/samba/smb.conf

Uncomment this line (remove the semicolon)
; name resolve order = lmhosts host wins bcast

and restart samba
sudo /etc/init.d/samba restart

For the record, I have it set up so netbios lookups are resolved through the DNS server.