Sometimes you can get an out of Terminal licenses message when connecting from a client, even if there are still plenty of licenses available. This can be due to some corruption in the client registry. You just need to delete the following key, and try connecting again. You should get the same license from the Terminal server.

HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\MSLicensing\Store\LICENSE000\ClientLicense