MS Terminal Server Licensing

We have a company that already had a terminal server (Windows Server 2003) in place. They have 25 per device licenses. In the license manager, these licenses show as being all used up. On top of those, there are also 3 licenses in the temporary license area.

Now, they want to split the load on their terminal server by adding another terminal server. We installed MS Windows 2003 on this server and configured it to look at the license server - which it finds.

What happens is that once the new terminal server finds the licensing server, we cannot log into it. We get this error on the clients:

"Because of a security error, the client could not connect to the remote computer. Verify that you are logged on to the network, and then try connecting again."

We figured it had be a licensing issue, but I thought that since it was working this way with the other terminal server, it shouldn't make a difference. One of the steps we throught we'd try is to add a fake 20 user Per-User TSCAL on the licensing server... not sure if that is causing us issues now or not but we cannot get rid of it.

Any help would be greatly appreciated!