NT Domains!?

I have a 3 domain NT4 network: DOM1, DOM2, and DOM3.
There are two-way trusts between all domains.
DOM1 handles user accounts.
DOM2 handles computer accounts.
So typically users login on a DOM2 computer with a DOM1
user account. But if I logon to a DOM2 computer with a
DOM3 user account I receve this message:
"The trust relationship between the primary domain and the
trusted domain failed. "

Shouldn't this work?! I know there is a full trust
relationship.
Any help would be very grateful!