Trusts – Domain can’t be contacted?

I have a hardware VPN setup between two offices, and need to establish a trust. The main office is Win2K Server, branch is NT4. I can ping computers in both offices by IP and by name (WINS servers in both locations). I can use Network Neighborhoodor Network Places to browse both networks, and can see all of the computers in the branch domain. But when I try to establish a trust, the Win2K server says that the domain “cannot be contacted”. What am I missing? I’ll be happy to provide more details, if you tell me what you need to know.