We got this message popping up on a Windows 2008 Enterprise server – we cloned 10 machines from the same template and only got this error on 1 of them – go figure. We used this to fix the licensing problem.

1. Run cmd.exe as Administrator
2. net stop slsvc
3. cd %windir%\ServiceProfiles\NetworkService\AppData\Roaming\Microsoft\SoftwareLicensing
4. rename tokens.dat tokens.bak
5. net start slsvc
6. cd %windir%\system32
7. cscript slmgr.vbs -rilc
8. Reboot
9. Key in your KMS key at the prompt after reboot – by this I mean the appropriate KMS client setup key, not the KMS key you apply to your KMS server.
10. Windows will activate from your KMS server
11. Reboot again to get rid of the black “not genuine” desktop.