Some XP Home users cannot connect to our Windows 2000 terminal server

When some of our XP Home users try to connect to our Windows 2000 terminal server they get the error that says they can't connect to the remote server, possibilities include network error or maximum connections have been reached. On the terminal server system log it logs event 1004 - The terminal server cannot issue a client license. They were able to connect in the past (within the past couple weeks)

We noticed that we didn't have enough licenses installed so we purchased two additional CALs and after that one of the users could connect again, but the others could not. They are still getting the same error and the same event is logged in the system log. There are still licenses available in Terminal Services Licensing, so we know we have enough licenses. The license server is functioning because one user who was unable to connect previously logged on this week and acquired one of the new licenses. The users who cannot connect to our server are able to access other terminal servers outside our network.

We have deactivated and reactivated the license server, reinstalled all the licenses, rebooted the server, made sure all updates have been applied. Does anyone know what we can do?