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.
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.