I was trying to join a fresh installed Windows 7 laptop into Windows Server 2003 and after entering the domain username and password, I got the error message
The specified domain either does not exist or could not be contacted.
How can I fix this?
Sounds like a problem with your DNS. Make sure your laptop is pointed to the domain controller for DNS. Without being able to query the _msdcs. service records, it won't be able to join the domain.
First you want to run "ipconfig /all" in a command prompt and see what your DNS servers are set to. If they are not set to DNS servers that are authoritative for your domain (or cannot forward the request to DNS servers that are) then you will not be able to find the _msdcs records. Try pinging the FQDN of your domain and seeing if you get a response.
If you can't ping the FQDN you will most likely need to change your windows 7 machine to use different DNS servers (ones that are authoritative for the domain).