When you try to join a Windows 2000 or Windows Server 2003 computer to a Windows NT 4.0 domain, you receive:

The following error occurred validating the name <Domain Name>. The specified domain either does not exist or could not be contacted.

This behavior indicates that the Windows Server clients are unable to resolve the NetBIOS name of the Windows NT 4.0 PDC.

If you use WINS to resolve NetBIOS names, verify that the IP addresses of the WINS servers are configured properly on the Windows 2xxx Servers.

Make sure that NetBIOS over TCP/IP is enabled.