From each domain can you ping the NetBios domain name? This may be the reason for the inability to connect with a trust. We had a similar situation a few months ago. There wree two NT4 domains, and one was upgraded to Windows 2000 domain with Active Directory. Once the upgrade had been completed, the 2 way trust quit working. We could ping the domain controllers, both by IP and by name. But the trust would not work. Each time, we received an error that stated it could not find the other domain. To check this, we attempted to ping the NetBios domain name from each domain controller. Failed.
Therefore, we added two lines to our HOSTS file. Below are examples for both Domain Controllsers. Substitute your own names and IP addresses.
This included....
---------------
192.168.1.2 NT4_PDC.DOMAIN1.COM NT4_PDC
192.168.1.2 DOMAIN1
---------------
10.10.10.2 W2K_DC.DOMAIN2.COM W2K_DC
10.10.10.2 DOMAIN2
---------------
NOTE: on the Win2k server, the AD domain name may be different from the NetBios domain name. You must use the NetBios domain name in the second line.
This was done to each domain controller and the information would point to the Other domain controller in the other domain. The first line locates the domain controller name and its IP address. The second line set the IP address to the NetBios Domain Name.
Once this was done, the trust was re-established.
Best of Luck.