When I ran into issues like these on a client computer, I made a little batch file that sits there automatically clearing the dns cache every hour. I didn't know what the fuck else to do.
Another thing to try would be using different dns servers
http://www.comodo.com/secure-dns/switch/ in case your ISP is just ignorant and stupid. I know Cox AND Comcast BOTH cause issues like these sometimes because they're not too bright. They're so worried about fucking with P2P traffic they end up fucking other shit up to hell