Are you using Network Level Authentication [NLA]? If so you could try disabling NLA on both the Remote Desktop [RDC] host machine and client as a test (ie. not a permanent fix).
http://theillustratednetwork.mvps.org/ScreenShots/RDC-NLAandServerAuth/Host-DoNotUseNLA.jpg
You can then try removing the certificate from your RDC host computer by going toStart | Runand typing mmc.msc, adding the certificate snap-in and deleting the Remote Desktop certificate then connecting again as a permanent fix.
http://theillustratednetwork.mvps.org/ScreenShots/RemoteDesktopCert.jpg
Note the comment about making sure the date and time is set correctly (on both the RDC host and RDC client) in this old thread from the Vista forums that deals with this issue...
MS-MVP Windows Desktop Experience, "When all else fails, read the instructions"