I upgraded from Windows 8 to 8.1 preview, and then Windows started to tell me to activate Windows in "Change PC Settings". However in "Change PC Settings" -> "Activate Windows" page I get error code: 0xC004F012: The Software Licensing Service reported that the call has failed because the value for the input key was not found.

In event log, I get this event:

The Software Protection service failed to start. 0x80070005

6.3.9431.0

Provider: Microsoft-Windows-Security-SPP

EventID: 1001

I tried to start the service manually in services.msc, and got Access Denied.

I used process monitor to see what's happening, and found sppsvc.exe is trying to delete this key and got Access Denied:

HKLM\SYSTEM\WPA\8DEC0AF1-0341-4b93-85CD-72606C2DF94C-6P-17

Then I opened regedit, made sure the sppsvc and Network Service accounts have full control over this key, and restarted the service, still got Access Denied. Then I tried to delete this key manually in regedit, and got this error:

Cannot delete 8DEC0AF1-0341-4b93-85CD-72606C2DF94C-6P-17: Error while deleting key.

You can use slui.exe 4 to active it by phone
1.  Press Windows key + X then click Run, then type:   slui.exe  4
2.  Next press the 'ENTER' key
3.  Select your 'Country' from the list.
4.  Choose the 'Phone Activation' option.
5.  Stay on the phone (do not select/press any options) and wait for a person to help you with activation.
6.  Explain your problem clearly to the support person.

Also you can type:
slmgr.vbs -ipk YOUR PRODUCT KEY

I tried slui.exe 4, but it stuck at the "Call and provide your installation ID" page, and nothing shows up.

Then I tried slmgr.vbs, got error code 0x80070426, then I ran:

slui.exe 0x2a 0x80070426

and it explains the error code means "The service has not been started."

I suppose "the service" here means the software protection service (sppsvc).

So it seems to me the root problem is that the software protection service cannot be started due to Access Denied when trying to delete the registry key.