I've had this problem, and I've solved it adding the logon credentials to the Control Panel / Stored User Names and Passwords (this is for a Windows XP / Windows Server 2003 host. There's the same thing in Windows 7 / Windows Server 2008 but it may be called a little different, like just "Users and Passwords". Sadly I don't have an English Windows 7 host at the moment).
You can also obtain the same results with the command line using
net use. For example if you need to add a share called SHIRE\Baggins (@Will Martin nice example! :) ) to a device called S: you type:
net use S: \\SHIRE\Baggins <password> /USER:<domain>\<user> /SAVECRED /PERSISTENT:YES
<password> <domain> and
<user> are obviously just placeholders for the actual logon data.)
This should mount the share AND add the logon credentials to the "Stored User Names and Passwords" control panel applet.
I hope this helps.