Is this a native or mixed mode domain?
Did the clients join the "pdc emultaor" type of domain, or the windows 2000 type domoain? (Win2k specifically is capable of joinig the nt 4 domain emulator, not sure if XP can or not)
 
the smb(server message block) error sounds like its joining the domain via netbios and not dns is why I ask, and the nt 4 pdc emulation does it this way.
Try this: disable netbios over ip and makje sure no netbeui is there. this way there is no netbios interaction. Make sure dns server info is set right on clients and see if you can do it right then.
To disable netbios over ip goto advanced tcpip properties>wins tab>DISABLE netbios over ip.

OK. First, make sure that the DC has its primary DNS IP set to itself in its network settings (such as the DC having 192.168.1.100 for an IP, in those network properties point it to itself). If you have other DCs hosting DNS, make sure that they (for now) point to the first DC that you setup. This DC will act as a temporary master server. Next, switch the DNS zone to "AD Integrated" along with "Allow Secure Updates", and then make sure that all of the clients have their primary DNS server IP pointing to this same server. The idea is to have a pristine zone where all of the systems are registering their records properly. If you have some static records setup (which you should if you were using a regular zone) try deleting one for one of your client PCs, and then reboot that client. When the client comes back up, it should properly register its name and IP. Give this about an hour to "cook", and then make sure that the record is in there. Once that's good to go, and you see the name and IP in there, do this for each server that is on the network. Starting with the DCs, reboot them one at a time and make sure that their records get registered properly.
 
What is probably happening is that you don't have the _msdcs, _sites, and various other SRV records registering in your AD. AD ABSOLUTELY POSITIVELY NEEDS THESE TO WORK. In the meantime, repeat this simple process for all of your systems. When you see all of your DCs and such registering their records and it's been working for about a day or so, you should remove the standard DNS zone copies from your other DNS servers, and add a new AD one for your domain. The DC should them pick up the copy from your existing DNS server (the first one that you converted to AD Integrated) and then these systems can be configured to point at themselves with their secondary preferred DNS IP pointing to another AD DNS box.
 
This resolves your interior resolution issues. Now, to allow the clients to resolve outside IPs you need to configure forwarders on the DNS boxes. I don't have a 2000 box available (we're all 2003 at work and that's all I run at home) but it should be similar from what I remember. Open the DNS console, right click on the server, and select properties. From there, you should see a "Forwarders" tab. Enter your ISP's DNS server IP in there, and this will tell the DNS server to resolve any name resolution requests for domains that it does not host by asking your ISP's DNS box.
 
I was just at an MVP conference this week in Seattle/Redmond and worked with the Directory Services team, and more specifically the DNS team regarding more simplified directions on how to setup DNS. I will be writing an article on how to do this very, very soon (hopefully this weekend).

Also, the NetBIOS thing is a bit different. Windows 2000 allows for NTLM/NTLMv2 credential resolution as a backup to Kerberos. This is why domains can be broken horribly but appear to be "working" at times. Windows 2003 AD environments are not as tolerant to misconfiguration anymore.
 
BTW, what was the reg fix you applied?

Article KB300684 describes the issues we were having and how it affected our replication process. What started this was a large amount of records needed to be tombstoned/cleaned out. Once those records were no longer present out DC replication died. We then reconstructed A Standard non AD integrated DNS structure on the DC's . AD replication was still failing between DC's located in different child domains. Netdiag and DCdiag would not assist in getting replication going. We applied the article registry fixes, rebooted DC's 1 at a time, and then ran netdiag and DCdiag against them. Once they checked out ok, we forced replication amongst the Boxes. Now our WINS structure has not been touched at all and was not in play in terms of troubles prior to this. Now what we see is machine accounts just poof! Gone! on the client side. The directory still has the account. We at one point thought it was the Time and Kerberos issue but we scripted in the net TIME command into our login process pointing to the enterprise root.

In terms of the 6 delegated zones necessary for AD, we checked those when we built the new primary zone at each of our domain levels. We run as a "Domain.Domain.Local" structure to keep our DNS internal and forward out to our DMZ forwarder, which then forwards out to our T1 and T3 Provider.

Does your DNS zone look like this?
 

 
If it does not have those _msdcs and such directories, then your AD will not work consistently (if at all). If you use a zone that allows for updates, then your DCs will publish those SRV records in those subdirectories.
 
Bear in mind that you will not have the "DomainDnsZones" and "ForestDnsZones" entries unless you are using Windows Server 2003 DCs with AD Integrated DNS.

I can send you full screen. do you have NTcompatible address?

Originally posted by harplayer:

Quote:I can send you full screen. do you have NTcompatible address? 
Just PM me if you can't post the image to a webserver.