I've finally managed to solve my own issue, after a multiple calls to Apple support and escalation to engineering support.
I used to use the Finder's "connect to server" command and type in:
"smb://server.host.edu/Sharename"
and this worked fine for a long time. All of a sudden it stopped working, and I was getting the error I described above. I called Apple support and we went through all sorts of troubleshooting but still couldn't fix it. Weird thing was, was that I was able to connect via the terminal just fine, and I had an iBook that could connect fine to the same server via the Finder.
The solution:
I stumbled upon a post in this thread:
http://www.macfixitforums.com/showflat.php?Board=tiger&Number=730956
which suggested a more complete format in the "Connect to Server" dialogue. So I tried this:
"smb://WORKGROUP;username:password@server.host.edu/Sharename"
Hey presto, my MBP connected! Even better, it will now connect using the old format: "smb://server.host.edu/Sharename" - weird.
I have a feeling the problem has to do with passwords and the keychain, because when it finally connected properly, I had a keychain dialogue pop up asking for permission to use the password for that server.
I hope this helps some other people out there.