Trusts are a lot harder then they at first seem, IMO. I went through this a couple of months back. Trying to set up a trust between 2 domains with a lot of distance between them.
So, here is all I did (and it is similar to what is listed in the above comments):
1. Both domains ran their own WINS Servers. Set the two WINS servers as push-pull Replication partners. (both PDCs must be WINS clients also)
2. Add each PDC and the domain in the LMHOSTS file of the other. (don't forget to NBTSTAT -Rafter changing LMHOSTS for the changes to take effect)
3. Add the ExpectedDialupDelay Registry entry in both PDCs. (technet article #Q163204)
4. When you finally do the trust itself in User Manager for Domains, I had to use the Domain Administrator password for both domains whenever I added THEIR domain as Trusted and Trusting. And they did the same for me on their domain: added my domain name as Trusted and Trusting, but they used THEIR Domain Admin password.
I no longer have the TechNet articles that told me to do all of these things. Each step was in a different one on domain trust.
Hope this helps