I've looked all over for a solution to this issue, but have yet to find one that works.
I've installed a fresh copy of Server 2008 R2 and enabled Remote Desktop. I connect to the server (by name or IP address) from a Windows 7 remote desktop client and get the attached error dialog.
I can certainly click "Don't ask me again" and get rid of it, but I'd rather fix the issue. If I click on "View Certificate" and then "Install Certificate", and place the certificate in the "Trusted Root Certificate Authorities," the error doesn't go away.
The server is not running AD Certificate Services. The certificate seems to be on a 6-month expiration cycle, which the server itself must regenerate on its own. I certainly didn't do anything to create it.
I can only assume I'm installing the wrong certificate, but I have no idea where the right certificate is. I've tried exporting the Remote Desktop/Certificates data from the MMC/Certificates snap-in, but I get the same results.