When installing a domain controller, Win2K Server gets cranky if it cant find a DNS server that handles SRV (service) records. The DNS servers for most major ISPs run BIND (short for Berkeley Internet Name Domain) v8.1 or later, which handles the records correctly. (As of this writing, the latest version of BIND is 9.0.1.)
The problem comes if you connect through a "minor" ISP that hasnt updated its DNS software. Not only will Win2K complain, but none of the Win2K Professional systems will be able to "see" the domain, even though you can ping the servers from the workstation.
The solution is to have the IP addresses of known-good DNS servers, install DNS on the domain controller, and forward the DNS through the domain controller to the known-good servers until the ISP updates its DNS servers.