I think this is a Vista problem, not OS X. I can connect to my Mac from XP when Windows sharing is enabled, but not from Vista. I get the same message you do.
The same happens for Vista -> Linux samba server.
Edit: Just tried Vista -> my employer's network shares, which run on Windows servers. No connection allowed. I'll have to play about with a bit more though.