Terminal Services licensing problem

I am working with a client that is using W2k3 AD server as license server, and a W2k Terminal server. CALS do not issue. Terminal Server is set to ‘per device’. 20 CAL win2000 Per Dev license had been installed initially. Also tried reinstalling the license as a 20 CAL Win2k3 per dev license. No success. It was suggested by another engineer that I reinstall the licensing server on the Win2k Terminal Server, but I want to see if there might be some other suggestions. Pardon the limited info, as I am out of my area of expertise on this.