I had s similar problem when changing service accounts in an Windows 2003 AD domain. The problem had to do with an Service Principle Name (spn) being registered under the old service account, which prevented the new service account from registering the spn. There a couple of ways to fix this:
1. Obtain setspn from Windows 2003 Support Tools, its available on Windows 2003 media and I think you can download it from Microsoft
2. Run setspn mydomamin\oldserviceaccount
3. You should see a list of spn's for all SQL Servers using the old service account:
4. Try deleting one spn on a test machine using setspn -D "MSSQLSvc/myserver.mydomain.com:1433" Mydomain\oldserviceaccount
5. Now try starting the SQL service under then new account
6. If this doesn't work try registering an spn under the new service account
If you prefer GUI's you can edit spn's with ADSIEdit:
1. Go to Start Run >> MMC >> Add >> ADSIEdit (I think this is available on any server or workstation with Windows 2003 Admin or Support Tools installed.
Needless to say running SQL Server under a domain admin account isn't a good practice after you get things working try scaling back the permissions to at least local admin on the box. Also I had grant the new service account permissions to register spns to avoid issues on new installs.