Windows 8 RDP Cannot Connect Schannel Event IDs 36870 36887

I have a fairly recent install of Windows 8 on a user's machine and I'm not able to RDP into it at all, it immediately fails and says it cannot connect. You can connect to the port via telnet and you can see RDP listening on the correct port via netstat. I've tried from both Windows 8 and Windows 7 hosts. I've seen the following errors in the event log when I attempt a connection.

Log Name:      System
Source:        Schannel
Date:          1/15/2013 5:07:05 PM
Event ID:      36870
Task Category: None
Level:         Error
Keywords:      
User:          SYSTEM
Description:
A fatal error occurred when attempting to access the SSL server credential private key. The error code returned from the cryptographic module is 0x8009030D. The internal error state is 10001.

and

Log Name:      System
Source:        Schannel
Date:          1/15/2013 2:50:14 PM
Event ID:      36887
Task Category: None
Level:         Error
Keywords:      
User:          SYSTEM
Description:
A fatal alert was received from the remote endpoint. The TLS protocol defined fatal alert code is 49.

I've also seen the warning below but am unsure if it is related.

Log Name:      System
Source:        LsaSrv
Date:          1/15/2013 5:06:28 PM
Event ID:      6038
Task Category: None
Level:         Warning
Keywords:      Classic
User:          N/A
Description:
Microsoft Windows Server has detected that NTLM authentication is presently being used between clients and this server. This event occurs once per boot of the server on the first time a client uses NTLM with this server.

NTLM is a weaker authentication mechanism. Please check:

      Which applications are using NTLM authentication?
      Are there configuration issues preventing the use of stronger authentication such as Kerberos authentication?
      If NTLM must be supported, is Extended Protection configured?

Details on how to complete these checks can be found at http://go.microsoft.com/fwlink/?LinkId=225699.