A client recently restructured their network as part of an office move, and when computers were moved to the new site several computers were unable to log in to the network, with a message that “The specified domain either does not exist or could not be located.”
In my experience, a majority of Active Directory problems like this are DNS related. Here are some useful tools to help diagnose problems.
Microsoft lists the DNS requirements for Active Directory in this article. The basic requirement is that _ldap._tcp.dc._msdcs.DNSDomainName must be locatable by the client. You can check this by running nslookup from a command prompt, then set type=srv, and then _ldap._tcp.dc._msdcs.mydomain.com (obviously, substitute your fully-qualified domain name for mydomain.com). If the client is unable to resolve this service address, they will not be able to log in.
Server problems, VPN problems, network card problems, and several other tests are available through NetDiag, a tool that is installable from the Support Tools of Windows Server installation CDs. A good basic tutorial is here.
Group policy troubleshooting, Kerberos authentication problems, and Active Directory replication failures (among other things) can be identified through DCDiag (also in the Support Tools). A good basic tutorial is here.
I would recommend using NetDiag and DCDiag to identify errors, and then Google the error that you are receiving.
You can find some more advanced usage scenarios on both NetDiag and DCDiag from Microsoft here.