Hab den Router Speedport W701V von T-Com.
Um das Problem zu lösen soll man einfach den Router neustarten.
Hat bei mir geholfen
Anscheinend waren ein paar DNS Einträge falsch. Das erklärt zumindest warum man mit einem Proxy noch auf Google zugreifen konnte^^