Googleovský DNS u mě pořešil Seznam, Skype, Google, české e-mailové účty a další, ne třeba stránky UPC, Microsoftu, Hotmail.cz, ale pro toho, kdo spěchá, tak provizorní řešení (ostatní běžte spát a dočkejte času )
http://www.pooh.cz/IT/a.asp?a=2016704
nebo zkuste proxy, anonymizéry atd.