I had the same problem for a long while, but tonight I seem to have solved it. This is how I did it. Hope it works for you and many others. My network storage is Buffalo Linkstation LS-CHL (I will call it LS-CHL below).
Sign-in your network storage device manually as before.
Go to Credential Manager under Control Panel-User Accounts. Look for your network storage device under windows credential and open it. Then select Edit. Replece the domain name in front of your user name (LS-CHL, in my case). Save.
Log off from you Windows account and then log in again. Windows will again say it cannot connect network drive. Open Credential Manager again and you will notice that your device is not there under windows credential.
Now connect your device again manually. Then in Credential Manager click "Add a Windows Credential": enter device name (LS-CHL, in my case) as internet/network address, user name (without domain name) and password. Save.
That is it. Log off window and then log back on, your device should be connected automatically.
The sequence is important.