W2K and NT 4.0 Trust Relationship

We are trying to set up a 1 way trust relationship between domains. The NT 4.0 being the Trusted and the W2K being the Trusting. When trying to establish the trust on the W2K box we get the following error:
The cannot be contacted. If thisdomain is a Windows domain, the trust cannot be set up until the domain is contacted. Click Cancel and try again later. If this is an interoperable non-Windows Kerberos realm and you want to set up this side of the trust, click OK.

Any help wouldbe appreciated.