I had this problem...it was prior to XP SP1 though.
Our problem was that the actual Domain rebuild was different. AD 2K3 native mode actually uses UID and OID so unless you rebuild it the MS way it most likely it is another domain with the same name. So until your PCs and Printer re-register with the domain they will not know it is the same domain.
The interesting part would be, from where do you manage the AD and with which tools.
Do it from another manchine which is completely up to date (I never manage AD from the server itself) and if you can get your hands on Hyena. This tool can save reports and settings from your AD (it could take some time to run the first scan, but it is great as a documentation tool as well)
Hyena will also give you the UID and OID (which you can get with LDAP queries as well)
Check from another machine to see if it detects the same domain. And also if you can rejoin a machine to the domain and see if when doing it, when you login with an account that you used previously if it created another container inside the machine (C:\Documents and Settings\username). Lets say you logged in before as [email protected], rejoined the pc and logged in again as [email protected], then you see C:\Documents and Settings\david and C:\Documents and Settings\david.domain then that means it recreated the account, and thus it thought the account was different (because UID wise it is)