Have just recently up-graded a 2003 DC with SP1 and some other known vulnerabilities. The DC is acting as an emulator master. After the up-grade I have noticed that our NT4 SP6a workstation's are not now logging on to the domain -"The system cannot log you on to this domain because the systems computer a/c in it's primary domain is missing.."

I do not want to roll-back SP1 etc.

Steps I have taken to rectify:

On the workstation, I removed it from the domain and put it into a
workgroup - rebooted. Deleted the machine account from the domain. Renamed the workstation to a temporary name - rebooted. Joined it to the domain again.

Ran a utility to give the workstation a new SID.

Has any one seen this issue before?