What version of Samba?
Vista default to using NTLMv2 and refuses to talk to anything less.
Late versions of Samba (~3.24+ or something like that) can be configured to work perfectly with this, but with earlier versions you need to reduce the security in Vista (google for the registry setting, I don't know it).
NTLMv2 has been around and used for ages, but Vista defaults to only allowing v2.