NT4 clients failing to connect to the Windows 2000 domain

Since NT4 relies on NetBIOS for name resolution, verify that your WINS server (you do have a WINS server running, yes?) contains the records that you expect for the 2000 domain controller, and that your clients have the correct address configured for the WINS server.