Most trust failures can be traced back to a name resolution problem. Are these machines in a lab or in production? If they are in production, make sure they are both pointed at the same WINS and DNS servers for name resolution. Make sure you can ping the flat domain name from each machine.
Since you need users from the NT domain to get to resources in the AD domain, you'll need to establish a trust from the AD domain to the NT domain. This makes the NT domain the "trusted" domain and the AD domain the "trusting" domain. The terminology can trip you up.
Use AD domains and trusts to set up the AD side of the trust. Use Usrmgr to set up the NT4 side. Configure the NT4 trust first so you can see the completion of the trust at the AD side.
If the system establishes the trust (after a long wait for name resolution), you should see both domains in the pick list of the Winlogon window of the clients in the NT domain. You'll also see the external trust listed in AD domains and trusts.
Test the trust by plucking a global group from the NT4 domain and putting it on the ACL of a folder in the AD domain. Then access the folder from the NT4 side.
If this fails somewhere along the way, check and double-check your name resolution. Send me a diagram of your network and the names and IP addresses of the WINS and DNS servers if you can't get the names to resolve.
This was first published in July 2001