Estiablishing Trusts

I have two domains within a tree. Both are Windows 2003 Servers running in Mixed Mode. I can validate the trust on one side, but on the other domain when I attempt to validate the trust I get the message: “Windows cannot find a domain controll for XXXXX.com domain. Verify that a DC is available and try again.”
The domain is there, and both can ping each other by IP as well as DNS. Suggestions?