I support many Macs that connect to an SMB share on a Windows Server 2008 R2 box. Occasionally I find that the Mac will try to connect and fail. The connection process will skip asking for credentials and there are none stored in keychain's password section. The server logs will show that the user tried to authenticate with invalid credentials. There are also no lingering connections from the server's point of view.
The work around that I've found is to use an invalid username or a username that isn't the user's in the connection string for SMB so
smb://domain;user@server/share instead of 'smb://server/share' this will force it to use the username I specified which the client doesn't have anything stored for. So it will then pop up the login window where the user changes the username to the correct one and user her password to connect happily.
Specific computer in question: 15" MBP running Snow Leopard (10.6.7 or 10.6.8)