If it really is the SQL Service that is no longer starting up, you should check the account that is used by the service.
So, go to Control Panel->Administrative tools->Services.
You will get a MMC, with a bunch of services. Right click to get the properties of anything that points to SQL Server (MSSQL, MSSQL$INSTANCE NAME, ...) and check what is entered in the 'Log On' tab.
If 'This Account' is checked (and it is your account that is shown there), you will have to reenter the (new) password there.
HIH
PS: this is if you're working on 2000. NT and XP are similar, but the menu structure and properties sheet are different.