Services Error by SQL Server Agent

Hi experts,
I am being plagued by the error given below by SQL Server agent.
This happens almost every time I restart the server that has been running for a day or two:

Could not start MSSQLSERVER service on Local Computer.
Error 1069: The service did not start due to a logon failure.
The SQL Server Agent uses a none expiring domain credential. I understand that this problem only happens when the profile being used by the SQL Server Agent has changed (password change). What puzzles me is that the login is ok and no changes has been made to it's password.
Can anyone please help me shed a light on this?
I am using SQL2k with SP3a.
Thanks
