Event ID 1004 Terminal Server 2008 will not issue a CAL

[xkaupx]

I am new to Terminal services and am working on a small deployment of
some XPe thin clients to replace aging machines. We have a small
domain so I am running Server 2008 with terminal server and the
license server on the same machine. Other machines, including the DC,
are Server 2003. Everything in the server manager seems fine, the
licenses installed ok and all 24 are available. I have Per User CALs
and the license server is in Per User mode. There are no problems
being reported by the License manager and it sees the locally
installed license server fine. The server added the Terminal server
license group to the domain fine. I have it set for forest discovery,
but being on the local machine it hasn't had a problem finding itself
yet.

When I connect to the server it reports a Event ID:1004 Cannot issue a
client license. The client connects and doesn't show any errors. The
client does however get what looks to be a console type session and
can see the server manager and administration tools. So instead of an
error they are just remoting the server desktop it looks like. Due to
permissions they can't do anything but run their programs, so a client
can't administer the server.

I have been digging around to find a solution and have come up empty
handed so far. I have checked the registry and the licensing server is
there. The server is part of the licensing server group.

I tried Reactivating the license server in case my CALs were
corrupted, but I still have the same problem.

It seems to be similar to this problem.
http://support.microsoft.com/kb/884570/en-us
Being Server 2008 though I don't think the hotfix should be, or would
be, applicable.

Maybe you guys have some ideas?
Thanks