samba - Apr 2004 - "DNS name does not exist" when joining Samba PDC domain

I am attempting to join a domain managed by a Samba PDC from several
Windows machines, both Windows 2000 Professional and Windows XP
Professional.  They all give a similar error.  The Windows 2000 error
gives me a URL that redirects to:
http://www.microsoft.com/windows2000/dns/tshoot/dns_tshoot2A.asp
The XP error is attached.

Any idea how I can fix this problem?  If necessary, I can modify the DNS
zone (on a BIND nameserver), but I've never had to do so in the past at
similar installations and I don't know what to add to BIND.

This is Samba 3.0.2a.  There is only one Samba server.  nmbd.conf
indicates that it is the domain master browser and a local master
browser.

Please let me know if you want my smb.conf.  If necessary, I can also
run tcpdump.

Thanks,
Jody
-------------- next part --------------
The domain name CMS might be a NetBIOS domain name.  If this is the case,
verify that the domain name is properly registered with WINS.
                                                                                
If you are certain that the name is not a NetBIOS domain name, then the
following information can help you troubleshoot your DNS configuration.
                                                                                
The following error occurred when DNS was queried for the service location
(SRV) resource record used to locate a domain controller for domain CMS:
                                                                                
The error was: "DNS name does not exist."
(error code 0x0000232B RCODE_NAME_ERROR)
                                                                                
The query was for the SRV record for _ldap._tcp.dc._msdcs.CMS
                                                                                
Common causes of this error include the following:
                                                                                
- The DNS SRV record is not registered in DNS.
                                                                                
- One or more of the following zones do not include delegation to its
child zone:
                                                                                
CMS
. (the root zone)
                                                                                
For information about correcting this problem, click Help.