We are in ntdomain DOMA, The terminal server is a member server 2003
standard SP1, with terminal services in per-user mode.
DOMA has two way trust with DOMB, this has been verified and works fine
for using eachothers AD objects in security settings for
files/groups/rights etc.
The domains are physically separated by a couple of routers and a
nortel firewall, the firewall has a big hole that allows anything to
and from all DC's on either side as well as the Terminal server.

The terminals servers (in DOMA) local "remote user" group and "power
user" group has DOMB's users group added to it.

User from DOMB has no problems accessing fileshares on this server or
any other DOMA systems, so authentication/trust is working.

When a DOMB user tries to log on to terminal services the DOMB\user
credential is accepted ok, but then a message says "The system, cannot
log you on due to the following error: The specified domain either does
not exist or could not be contacted" (Note, this is not the same as if
you put in the wrong password for the same user).

In the application event log I get this:
Event Type: Error
Event Source: Winlogon
Event Category: None
Event ID: 1219
Date: 6/16/2005
Time: 2:29:27 PM
User: N/A
Computer: TSERVER
Logon rejected for DOMB\ubergeek. Unable to obtain Terminal Server User
Configuration. Error: The specified domain either does not exist or
could not be contacted.
0000: 4b 05 00 00 K...

I have been messing with this for some time now, and I discovered that
if I first log on to the terminal server locally on the console with
this DOMB user, this user can now use terminal services at will without
a problem, even after deleteing the users profile directory...

And because of this last one it really strucks me that there must be
something buggy about first time authentication for trusted foreign
domain users with terminal services? or some awkward permission
settings of sorts to allow this foreign-domain object to be stored in
some container for "good guys"?

Any clues?