I think it's a DNS issue. At work, I was switching between two proxy servers that go out in two different states (and thus two different DNS servers), and I was able to get through on one but not the other. This was two weeks ago when people first started having problems. Switching back and forth, it was repeatable.
You could try manually adding a public DNS server, there has to be one out there that works.