I came across this error message today when building a virtualised SharePoint/MOSS farm on Windows 2008 with SQL 2008.
When trying to install SQL 2008 and specifying a domain account for the SQL service account, the installer kept telling me that the credentials were invalid.
I (temporarily) adding the service account to the local admin group on the SQL server, but the account name did not display. I tried adding the service account again, only to have windows tell me that the user was already a member of the group!
I proceeded to spend a couple of hours fiddling with the firewall settings and Kerberos only to have it dawn on me that I had forgotten to SYSPREP the machine before I'd cloned it...
I then went back to the template VM only to find that Sysprep no longer works on Windows 2008. Apparently, it's been replaced with a new tool which generates the inf via XML. I downloaded it in haste, discovering that it's designed for Windows images (I'm using Vmware).
Fortunately I remembered that there was another way to "de-identify" the virtual machine....NewSid ! Fortunately it still works on Windows 2008.
After running it I removed the computer from the Domain and deleted the computer account. I then rejoined the domain and the SQL installation went smoothly.