For anyone who runs into this issue and comes across this post while Googling for a solution...
I ran into this bandsaw with a handful of Windows 2008R2 servers - a software update to the Microsoft Remote Desktop client is definitely responsible. My mac updated itself to Remote Desktop 10.8.2, and suddenly I lost all access to all of my older servers.
My fix was to turn off Microsoft's autoupdater, uninstall Microsoft Remote Desktop (I had it handled using homebrew), then went out and grabbed the old installer package - Homebrew has the full URL in the homebrew-cask repo; use this as a starting point -
https://officecdn-microsoft-com.akamaized.net/pr/C1297A47-86C4-4C1F-97FA-950631F94777/MacAutoupdate/Microsoft_Remote_Desktop_<insert_version_number_here>_installer.pkg
I went with a version I know worked in the past - 10.7.10.
Hope this helps!