It sounds very similar to an 8.1 DNS / WINS issue experienced here, so when you get a moment, try the following:
Go into "Network And Sharing Centre" (rightclick on network icon bottom-right of screen)
Click on "Change adapter settings"
Rightclick on the icon of your active network adapter, and select "Properties" menu entry
Find "Internet Protocol Version 4 (TCP/IPv4) in the list displayed (usually at the bottom)
Once selected, click on Properties button.
Click on "use the followng DNS server addresses"
Enter two public DNS addresses below, eg Google DNS (8.8.8.8 & 8.8.4.4), OpenDNS (208.67.222.222 & 208.67.220.220)
Finally, hit OK on that window, and Close on the Properties window.
For belts and braces, do a system restart, give it a try and test, and hopefully your problem is fixed. 
(Well, at least in the short-term, but of course you're now at the mercy of latency time to google's or OpenDNS' nameservers until MS fix the problem. Unless. Unless...
...unless you go to Gibson Research, download their DNS tool, and find something "closer" and faster. Find it at https://www.grc.com/dns/benchmark.htm, let it run initially, then if you're outside the USA, take the "Build Custom List" option and follow the instructions.)
HTH