Maybe this has been said before, somewhere, but I never ever found it. I work at Uni IT group, and needed to get Ubuntu playing nice with our windows shares.

This Post:
and this one:
and this one:
all discuss this problem, with all sorts of ideas to fix it.

We don't use Vista, but we do force NTLMv2 authentication only on our Windows XP shares for security reasons. In Vista this is the default way of sharing files. smbclient works just fine from the command line, but that is messy for our users.

The common idea is to add
client ntlmv2 auth = yes
to /etc/samba/smb.conf. This works for smbclient, but not for nautilus, for the simple reason that nautilus sources $HOME/.smb/smb.conf, NOT /etc/samba/smb.conf.

Thus this is the fix.

As your own user:
mkdir ~/.smb
echo "client ntlmv2 auth = yes" >> ~/.smb/smb.conf
Just to note, I do work in a domain environment. So I also added "workgroup = server" to my configuration. Doubt this will break anything for everyone else. Hope this fixes things, or at least clarifies them for some people.