Ever since Apple came out with Mountain Lion, support for Microsoft’s RDP protocol to remotely administer Microsoft Windows desktops and servers has been flaky or just not working. Oddly enough, people were more succesful using the reverse-engineered CoRD client. But this reverse-engineered solution had trouble with newer Windows versions, just because RDP is a bag of hurt.
If you have any issues using the Microsoft Remote Desktop Connection Client with Windows Vista, Windows 7, Windows Server 2008 and higher, you should check out this thread on TechNet.
At the end, someone links to a new version of the client, hosted on Dropbox.
This claims to be version 2.1.2 of the Microsoft Remote Desktop Connection Client for Mac. Try it out and see if it fixes your issues.
Update
Just around the release of OS X 10.9 Mavericks, Microsoft has released two Microsoft Remote Desktop apps in the Apple App Store. One is both for iPhone and iPad, and another one is an app for OS X. – W, 28th of October 2013