Ondrej Sevecek's English Pages

If you make Terminal Server forget the old/archived certificate then it finds the new certificate and works.  This seems to be safe and is instantly effective.  No need to restart services or reboot following the change.  The below command does it and reveals the registry value that can be deleted.

reg.exe delete "HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\Terminal Server\WinStations" /v "TemplateCertificate" /f

There are many misdirecting errors messages associated with this problem.  I was seeing "The computer requires Network Level Authentication, which your computer doesn't support." at the client.
The server would concurrently show system event log Schannel event id 36870 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.
Alternately if NLA wasn't required the client would complain that it was unable to verify the server.