Remote Desktop error in the licensing protocol

I have users getting this error when they try to use Remote Desktop from new pc's they have at their homes. The pc's came with the RDP already loaded. I looked it up on Microsoft's TechNet & it said to delete the MSLicensing from the registry which I did & that didn't fix the problem. I just upgraded the RDP to version 6 deleted the MS Licensing from the registry again & it still gives me the same error. I have it set to always connect even if authentication fails & to automatically detect TS Gateway server settings. This is the error we get back. Any idea's what I may try?

The remote computer disconnected the session because of an error in the licensing protocol. Please try connecting to the remote computer again or contact your server administrator.

Thanks
Steve