Assuming it's Terminal Server (Application Mode), I would assuming removing Terminal Server from the server should do it. But probably a bad guess (Assuming it's not a licensing issue before as mentioned).
The other one, (I'll have to dig in my notes) is there is a registry key on the client computer indicating it's license. You may have to delete that key on the workstation (not the server).
The other bit to seeing what does work is can you connect if you go to start Run (or just Start and start typing away in Vista/2k8)
mstsc -console (XP/2003)
mstsc -admin (Vista/2K8)
to access a console session. (Local console, uses RDP to connect, is not technically a terminal session)
I'll see if I can find that registry key client side.
Well all else fails, make an offering to the computer gods. Preferably in small unmarked bills.