I came across an issue where I could no longer remote desktop to a Windows Terminal Server after installing Remote Desktop Licenses on it and I got the above error. It turns out that this is a bug and you need to update to RDC for Mac v 2.1.2 which can be downloaded from the following link;
http://www.trailblz.com/kb/?action=view&kb=175&cat=12
RDC for Mac error – Problems during the License Protocol