This problem keeps coming up every now and then so I thought it would be good to document it. If you get licencing error messages when you connect to a Terminal Services session on a remote server then this might fix the problem (you might also get this error if you use the Remote Application Service (RAS) here at Newcastle).
Create a backup of the MSLicensing registry key and its subkeys on the client, and then remove the original key and subkeys by doing the following:
1. On the client, navigate to the following registry subkey: HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\MSLicensing.
2. Click MSLicensing.
3. On the Registry menu, click Export Registry File.
4. In the File name box, type mslicensingbackup, and then click Save.
5. If you need to restore this registry key in the future, double-click mslicensingbackup.reg.
6. On the Edit menu, click Delete, and then click Yes to confirm the deletion of the MSLicensing registry subkey.
7. Close Registry Editor, and then restart the computer.
When the client is restarted, the missing registry key is rebuilt.
Its probably also worth checking to make sure you have the RDP 7 client installed, see http://blogs.msdn.com/rds/archive/2009/10/28/announcing-the-availability-of-remote-desktop-connection-7-0-for-windows-xp-sp3-windows-vista-sp1-and-windows-vista-sp2.aspx (we rolled this out on campus at the end of 2009)