This issue happens on XP SP3 and on Win7 SP1. The service is configured to run using a service account to logon as a service. When I manually enter the password it is accepted and is given logon as a service right. Then once the computer is rebooted the service does not start due to no password saved.
below is the error
Event ID 7041 service was unable to log on as contoso\$serviceaccount with the currently configured password due to the following error: Logon failure: the user has not been granted the requested logon type at this computer. This service account does not have the required user right "Log on as a service."