I loathe those problems that require lots of fiddling but ultimately turn out to be very simple to fix! Hindsight is wonderful thing!
Today's challenge was making a Remote Desktop connection from my MacBook to my home server running Windows 8. This worked perfectly until I recently upgraded to Windows 8.1.
After installing Windows 8.1, Remote Desktop would fail to connect, reporting:
Remote Desktop Connection cannot verify the identity of the computer that you want to connect to.
Online you will find various possible solutions, ranging from changing some options, combinations of setting the domain field, removing stuff from your Apple Key Chain or even some hardcore registry editing.
However, as I said, the solution is pretty simple... just upgrade to the latest version of Remote Desktop client! My RDC client was originally installed alongside Microsoft Office for Mac and no updates are reported (the latest is 2.1.1). However, if you look in the App Store, you'll find Microsoft Remote Desktop.
It looks to be a completely new application, which in my opinion is much better than the original! Once I installed this, I could connect to my Windows 8.1 machine without any problems.