I must have come across this stupid error a dosen times and it is often solved by simply changing the Windows machine's Network ID or by running the Network Connection Wizard thingy in the Control Panel -> Connections page.
This time though, we had a computer playing hardball and was only solved by doing the following (from PChuck's Network):
Download and install the Windows 2003 Server Resource Kit Tools.
Click Start | All Programs | Windows Resource Kit Tools | Command Shell.
Type these three lines, one at a time, at the command prompt. The ntrights
commands are case-sensitive, so type them exactly as shown. Note the "+r" in
the second one and the "-r" in the third one:
net user guest /active:yes
ntrights +r SeNetworkLogonRight -u Guest
ntrights -r SeDenyNetworkLogonRight -u Guest
And that solved our problems. Well for most guys. For some reason my Vista still did not want to connect. I changed my Network ID to be same, and whala! It worked! This is a bit peculiar considering that I was able to connect across different Network ID's on my previous XP machine. I don't have time to double check and validate that now though.