I have been in the technology industry for more than 25 years now and I have dealt with my fair share of connectivity issues. In the last decade or so a good 85% or more of the issues I have encountered have been DNS issues. There is a very easy solution to fix the problem (temporarily) and to confirm that the issue is DNS.
Simply add a record to the local hosts file:
Start | type Notepad | Right-Click on Notepad | Run as Administrator
Answer Yes to the UAC prompt (if there is one)
Inside Notepad click the File menu | Open
type in the bottom c:\windows\system32\drivers\etc\hosts and change the type box to all files
then click Open
This will open your local hosts file. Now you will need to know the IP address and the name of the machine you are trying to establish connectivity to.
move the curser down to the bottom of the file and type in the IP address followed by at least one space then the name of the server. You might want to make two lines for the server. One with the fully qualified domain name and one with just the server name.
Then click the File menu and save
Try the connection again. if it magically starts working you have confirmed that you have a DNS issue. This will not FIX your DNS issue. It is a workaround until you get time to investigate why DNS is not working.
You can safely close the notepad box.
Once you have resolved the DNS issue, you should go back and remove the lines you added.
In my demo environment, I often do not fire up the DC so I use hosts file entries all the time. The problem with it is if I change the IP address of the server, it will update DNS but I will no longer be able to get to it as the Hosts file cannot be updated automatically.
When I get a chance, I will try to post more about DNS as I know it is a problem for many people and most of the documentation on it can be very confusing.
You may also be interested in... Resolving Network Issues-You Might Not Have Permission To Use This Network Resource which goes into a bit more detail about DNS and how you might resolve a particular DNS problem