I've been working on a project that required a domain controller and application server to test the application.
I used VPC 2004 to build 2 Windows 2003 Servers for this. I initially created 1 VPC and performed the upgrades / patches, etc. Then I'd copy this file, renaming it and placing it in a different folder for the virtual hard disk, etc.
When I promoted my DC and joined it with the application server, all went well - until I tried to logon to the DC. I received the above mentioned error.
Because I created only ONE Windows 2003 Server, the SID is the same on both of my virtual machines because I simply copied the virtual hard drive and renamed it. If you have MSDN and you're wanting to save time - why install Windows 2003 more than once, right? Well, wrong.
Fortunately I haven't been the only one to see this. You can download NewSID from SysInternals (http://www.sysinternals.com/Utilities/NewSid.html) and it will change the SID on the server you are wanting to connect to the DC with. They even include the source code - for educational purposes.
NOTICE: Before running the NewSID application, MAKE SURE YOU ARE NOT JOINED TO THE DC - otherwise, you'll have to muddle through logging on locally, disconnecting, and rejoining the DC. When the SID is changed, and if you are connected, the new SID generated has NO permissions. A no brainer perhaps, but I just wanted to mention this here.