Did you but Per User or Per Device licenses?
If Per User, is the Terminal Server (not the Licensing Server!) set
to use "Per User" licensing? The default is "Per Device".
You can check this from Administrative Tools - Terminal Services
Configuration - Server Settings
If it's set to Per Device mode, it will look for a Device TS CAL
and will not issue your Per User TS CALs.
Check this article, it explains that even after you have
switched licensing mode on the TS, your Per User TS CAL count will
not be decremented:
822134 - The Function of Terminal Server CALs in Windows Server
2003
http://support.microsoft.com/?kbid=822134