Windows 2000 service logon failure

I have two services that use an active directory account to logon. Each time I reboot the machines, the services fail to start due to a logon failure. I open the service properties, try to start the service and get the same failure. I retype the password (using the same password as before), restart the service and everything is fine. I do not understand why the reboot fails yet typing the same password works. Any ideas?