On June 1, 2016, Microsoft released an update to it's Remote Desktop client for Mac OS X via the Mac App Store. The update to version 8.0.32 broke some functionality for people. The most commonly reported error I have seen is "Connection reset to peer" before authentication.
Sadly, unless you have a Time Machine backup to grab the old version from you are likely going to have to find an alternative. If you do happen to have an older version that isn't broken let me know and I will gladly host it for all to get here.
An alternative is to use a beta version of the Microsoft Remote Desktop for Mac. This is a beta version; as such you should expect some beta like functionality. However, my limited testing indicates that where Microsoft Remote Desktop for Mac version 8.0.32 falls flat on its face this beta version appears to work.
If this beta version disappears off the web for whatever reason I have made it available: Microsoft Remote Desktop for Mac version 8.2.22 (126.96.36.1998) via chrisshort.net