I was having trouble connecting with the Remote Desktop protocol to a server. The error returned by the Remote Desktop Connection Manager was 7431. Using mstsc.exe the error was more descriptive and indicated a time difference between the client and the server. I verified that the time difference was not the case.
Coincidentally, a support request came in from a user that was related to that server. This led me to troubleshoot another issue and that’s when a realized that the problem was a misconfiguration in the DNS settings. We’re retiring some old DNS servers that were on the same subnet as the problematic server, but the new DNS servers are on a different subnet. The issue boiled down to the server not being able to reach DNS (and other servers) and therefore having some trouble verifying the connection security. Once we rolled back the DNS change, everything started working normally.