Error in creating a mailbox on exchange 5.5 says trust failed between primary and trusted domain

I have Exchange 5.5 setup on Windows 2K in a W2K3 domain. If I try and
add a mailbox without a primary account assigned to it I get an Error that
says The trust relationship between the primary and trusted domain failed.
Now I do have several NT 4.0 domains that have a two-way trust between them
and my 2k3 domain. If I create a new account or assign to an existing
account I do not get the error.

Any Ideas ?


.