Terminal server logs off users after 5 minutes

We have the following domain setup:

• Domain Function level: Server 2008
• 5 Server 2003 terminal servers
• 5 Server 2008 R1 terminal servers
• 150 staff who use mandatory profiles on their PCs
• Those staff do not have a terminal server profile path in AD as we found it meant for quicker logons.

Our issue is that when the staff log onto the Server 2008 terminal servers they are automatically logged off after just over 5 minutes.

In the security log of the terminal server is this event:

    User initiated logoff:

Subject:
    Security ID:        contoso\bloggsjoe
    Account Name:       bloggsjoe
    Account Domain:     contoso
    Logon ID:       0x1c66ba

This event is generated when a logoff is initiated but the token reference count is not zero and the logon session cannot be destroyed.  No further user-initiated activity can occur.  This event can be interpreted as a logoff event.

and then 10 seconds later is this:

An account was logged off.

Subject:
    Security ID:        contoso\bloggsjoe
    Account Name:       bloggsjoe
    Account Domain:     contoso
    Logon ID:       0x1c66ba

Logon Type:         10

This event is generated when a logon session is destroyed. It may be positively correlated with a logon event using the Logon ID value. Logon IDs are only unique between reboots on the same computer.

The end user gets a message that they will be logged off in 2 minutes. There is no event recorded on the client machine (all Windows XP)

I've looked through the Terminal Services Configuration but the disconnection time is set to 2 hours and the Active Session Limit is set to "Never"

We have used terminal server mandatory profiles but that made no difference. The problem does not happen for administrators.

I wonder if any of you can help?

UPDATE1: For people asking about CALs, the DC is the terminal server licensing server and always works well. At the moment on the 2008 TS it shows as 426 CALS available for clients. They are licensed in per device" mode.

UPDATE2: There is something odd about the timings in the Terminal Services Manager. Many dates show up as the time that all computer times are worked from - 01/01/1601. Here is a screenshot as the problem user is logging on:

Larger image

When the username is resolved the time is corrected also - does that make it look like the user have been loggged on for over 400 years though?

Larger image

Have any of you seen this kind of thing before and would you know how to resolve it? I've checked with another site and the 1601 year is not the same there.

UPDATE3: Forgot to say that the logoff does not happen because of 5 minutes of inactivity - it happens no matter what the user is doing.

UPDATE4: Licensing issues. It looks like there is some kind of terminal server licensing issue - though none of the servers are giving licensing errors. The licensing server is a DC which showed plenty of valid licenses available (all Per Device) it showed a lot of temporary device CALs issued however and those could not be revoked. I completely removed the licensing role and set it up again. This left me with 500 Server 2003 and 500 Server 2008 Per Device CALs free, but only a few machines are being allocated a CAL, some are being issued temporary CALs, but most seem to be not showing up at all. There are some devices being listed as "unknown" as the machine name, so I'm sure this must be at the heart of the licensing problem - though I have no idea if this is in any way connected to my logon problems. BTW, when I click on the Terminal Server Configuration page on any terminal server they report that there are no licensing issues detected.