Event ID 1057 - The Terminal Server has failed to create a new self signed certificate

If you receive Event ID 1057 - "The Terminal Server has failed to create a new self signed certificate to be used for Terminal Server authentication on SSL connections. The relevant status code was Key not valid for use in specified state" from source TerminalServices-RemoteConnectionManager in the System event log, you may have an issue with a lot of strange advice. For me, none of which worked. I finally figured out the problem.

The conditions you'll probably also notice is that you can't remote desktop into the server until you remove the "Allow connection only from computers running Remote Desktop with Network Level Authentication" checkbox in the Remote Desktop Session Host Configuration's RDP-Tcp properties General Tab or from the System settings under the Remote tab by changing the radio button back to "Allow connections from computers running any version of Remote Desktop (less secure)".

In my case I had already tried a lot of the advice like deleting the self-signed certificate and rebooting (MMC/Certificates/Local Computer/Remote Desktop) And deleting these keys and restarting:
“HKLM\SYSTEM\CurrentControlSet\Control\Terminal Server\RCM” > Certificate “HKLM\SYSTEM\CurrentControlSet\Control\Terminal Server\RCM” > CertificateOld “HKLM\SYSTEM\CurrentControlSet\Control\Terminal Server\WinStations” > SelfSignedCertificate

I also deleted the Host Configuration's RDP-Tcp connection object all together and restarted the Remote Desktop Services service.

What did finally work, I noticed that we had a bunch of crypto keys that looked like this:
C:\ProgramData\Microsoft\Crypto\RSA\MachineKeys\f686aace6942fb7f7ceb231212eef4a4_XXXXXXXX

I moved them all to a subfolder so there were none left in the MachineKeys folder. I then opened the MachineKeys and re-applied the full-control permission to the local server administrators group. (Security/Advanced/Change Permissions/Replace all child object permissions) and applied this.

I then restarted the Remote Desktop Services service and this time I didn't get the error about the certificate. I changed the security setting for RDP back to secure and was able to log on through Remote Desktop.