You can tackle this problem two ways, first by just clearing the cache, but also by restarting the DNS client service, which handles caching of DNS lookups.
UPDATE: We have a newer version of this article available, that has been updated for Windows 10, 8, and 7.
Clear DNS Cache
Open up an administrator mode command prompt by right-clicking on the Command Prompt in the start menu and choosing “Run as Administrator”
Now type in the following command:
This usually clears up any issues that might be occurring. Note that if you are using Firefox you should probably also close and reopen, because Firefox has a DNS cache as well.
Restart DNS Service from Command Line
Open up an administrator mode command prompt as above, and then type in the following commands:
I usually use the command prompt for this, since I already have it open for the previous step.
Restart DNS Service from Services
Open up Services in the control panel, or by just typing services into the Start menu search box. Once there, find the “DNS Client” service and click the Restart Service button.
By this point I’d hope that things are working again. Note that these instructions should also work for XP.
Update: Reader Fred wrote in to mention that you can also use the “Repair” option in XP or Vista. Just go to the network connections list in control panel, find the adapter and choose Repair for XP or Diagnose for Vista.