I run a domain with two Windows NT 4.0 Service Pack 6a (SP6a) domain controllers (DCs)—one PDC and one BDC—and about 1500 Windows 2000 workstations. When I try to add a new Win2K computer to the domain, I get an error message that says the domain couldn't be contacted or doesn't exist. I can ping the PDC and BDC, and sometimes the new computer even shows up in Server Manager. But if I try to remove that computer name from the Server Manager list, I get a message that says This computer is not actually a member of the domain and will be removed from the list on the next refresh (in approx. 15 min). I've removed the BDC, upgraded the BDC to a PDC, and manually synchronized the DCs. I can add NT 4.0 machines with no problem. Have you ever run into this situation?
You might need to try a few things to resolve this problem. The difficulty might be that your DNS server doesn't support SRV records. If it doesn't, open the Control Panel Network and Dial-up Connections applet on the Win2K machine, open the NIC's Properties dialog box, and double-click Internet Protocol (TCP/IP). Click Advanced to open the Advanced TCP/IP Settings dialog box, and go to the DNS tab. Add a fixed IP address for a DNS server that supports SRV records to the list of DNS server addresses. Then, try joining the Win2K computer to the domain again. If you're successful, you can then replace the address you added with the address of the original DNS server.
If that technique doesn't do the trick, go to the WINS tab of the Win2K machine's Advanced TCP/IP Settings dialog box. Select the Enable NetBIOS over TCP/IP option. If you're using WINS, add the WINS server address to the WINS address list. Otherwise, use an LMHOSTS file for name resolution. If you don't want to use NetBIOS, you can disable it after the machine has successfully joined the domain.
If you're still having trouble, make sure you aren't using a Canonical Name (CNAME) record as the SRV record's host. Use a host record instead.