After connecting to a Terminal Server successfully, you may get an error indicating that a terminal services license is expired or no longer available - please contact your network administrator.

You need to remove the temporary Terminal Services license from your computer, the one trying to make the connection. The fix involves making changes to your computer registry. Though the fix is not difficult, adjusting the registry, if done incorrectly, can cause your computer to malfunction. If in doubt, have your network or IT administrator make the changes. If making the changes yourself, you should always backup your registry settings first.

The following Microsoft Knowlegebase article explains the reason and the detailed fix: http://support.microsoft.com/default.aspx?scid=kb;en-us;187614


Essentially, you need to delete the entire MSLicensing key from the registry:
Thirty-two bit RDP clients store their license under the key HKEY_LOCAL_MACHINE\Software\Microsoft\MSLicensing.
 (Dont delete MSLicensing, just the key(s) beneath it).