Sounds like a DNS issue to me - which DNS servers are you using?

Try changing to the free Google servers at 8.8.8.8 and 8.8.8.4.