"The Client could not establish a connection to the remote compute

Background:
-Server running Windows 2000 Server SP3 with Terminal Services (application
server Mode)
-Workstations running Windows XP SP1a
Behavior:
-When attempting to connect to the 2000 Server via RDP from several (not
all) XP workstations one receives the following error message:
"The client could not establish a connection to the remote computer.
The most likely causes for this error are:
1) Remote connections might no be enabled at the remote computer.
2)The maximum number of connections was exceeded at the remote computer.
3) A network error occurred whle establishing the connection."

What is odd here is that several XP workstations have not problem at all
connecting. The ones that are unable to connect only have a problem with
this particular server, that is to say they are able to connect via RDP to
several other TS servers without any problems at all.

Note: There is a log in event viewer which states "The terminal server
cannot issue a cient license"
We do not have a license server up and running, is this required? If so why
do some clients connect just fine without this?

Any ideas? Suggestions?
Thanks