FC,

On the TS, does the appropriate group have both the 'log on locally' as well
as 'access this computer from the network' rights?  Are the users attempting
to log on to the TS a member of the correct group when you go into the
Terminal Services Configuration Manager?  If you go to each user account
object in ADUC in the Terminal Services Profile tab there is a checkbox
entitled "Allow logon to Terminal Server" that needs to be checked.

Is the error code that you indicated below - is this the exact error
message?  Did you take a look at the event ids?

HTH,

Cary