I actually had an identical problem on my Exchange server. I solved it by renaming the account, changing the logon credentials in the Service Manager, then renaming it BACK and changing the Service Manager entries again. Scientific? Not really -- more like a big random guess. But it seems to have worked, so give it a try.
This was first published in March 2003