This issue was driving me mad, followed al the hints from "Google" but no solution at all. So your on your own.
Running OS windows 2008. Application Backup-Exec 12.5
The account involved in this issue has given logon as a service rights. Again the same troubles. mmm the next thing, creating a group policy DLG_ExecuteBatchTasks. This seems to be the solution because due to this policy the involved account may run local batch tasks.
After logon again I was able to browse the network, credentials were never lost again.
Thanks to Marc for assisting on this while I had a few days holiday!