Hi!
That is almost certainly a DNS issue. When setting up a trust, you need to have name resolution in both directions. You can do this with lmhosts files, WINS or DNS.
DNS is the easiest solution. You need to create secondary zones on each domain for the opposite domain.
For example, domainA would have a secondary DNS zone for domainB, and domainB would have a secondary DNS zone for domainA.