Adding a Server to a Domain

Ok, here is my scenario: I have installed NT 4.0SPp6a server and am attempting to join my domain. I establish the account in the PDC and then join the domain from this new server. This portion is successfully (I receive the message Welcome to XXX domain). When I attempt to view the properties of this server from the PDC I receive the msg: “The trust relationship between the PDC and this server failed”. I have setup the shares, users/permissions, groups, etc and still am not able to establish a trust.
Thanks to all who can help!
Gregg