This error is usually the result of corruption in the Licensing store. The solution is to recreate the store.
1. Stop the slsvc service
2. Navigate to C:\Windows\Service Profiles\Network Service\AppData\Roaming\Microsoft\SoftwareLicencing
3. Rename tokens.dat to tokens.bar
4. Start the slsvc service
5. From C:\Windows\System32\cscript slmgr.vbs -rilc (It may take a long time for this to complete)
6. Restart the computer twice.
It should prompt for the licence key