Figured it out. My CAL licenses are installed as "per User" and
TS was configured as "Per Device".
Here is M$'s write up on it:
Event ID 26: Your terminal services temporary client license will expire
in N days
http://technet.microsoft.com/en-us/library/cc737482%28WS.10%29.aspx
And here is the fix:
http://technet.microsoft.com/en-us/library/cc994792%28WS.10%29.aspx
The temp licenses will still show as they are the previous "devices"
that got licenses. They will eventually age out.
And, a bug that the above links do not discuss, but the M$ tech
confirmed over the phone: "Per User" licenses are not tracked.
So, you will not see them checked out. You will know when you
got things configured corrected when your users stop getting
warnings about their temporary licenses expiring.
Hope this helps someone else,
-T