Wenn du Google in diesem Bezug nicht genug vertraust, kannst du das mal nur zum Testen einstellen. Ansonsten klingt das hier (
https://developers.google.com/speed/public-dns/privacy) aber auch vernünftig (zum Beispiel, dass die Daten nicht mit denen von anderen Google Diensten vernknüpft werden usw. - am besten einfach mal selber überfliegen)
Geh in's Startmenü, gib ein "Netzwerkverbindungen anzeigen", klick dort auf die aktive genutzte LAN-Verbindung (die ohne rotes Kreuz...) mit rechts auf "Eigenschaften". Da ich mal davon ausgehe, dass du noch IPv4 verwendest

klick einmal "Internetprotokoll Version 4" an und dann auf "Eigenschaften". Die Option "Folgende DNS-Serveradressen verwenden:" aktivieren und bei "Bevorzugter DNS-Server:" die IP-Adresse "8.8.8.8" eingeben. Zum Testen reicht das erstmal (für die permanente Einrichtung in dem Feld darunter "8.8.4.4" auch noch eingeben). Wenn du das wieder zurückstellen willst, gehst du genauso vor, nur dass du die Option "DNS-Serveradresse automatisch beziehen" auswählst. Das ist der schnellste Weg. Sonst bliebe nur die Alternative, dass über die Routeroberfläche für alle Netzwerkgeräte zu konfigurieren (und das solltest du lieber lassen, wenn du keine Ahnung davon hast, nachher zerschiest du dir dein Internet noch komplett

).
Ansonsten: Hast du beim Fritzbox-Neustart das Gerät auch mal für 5 Minuten vom Strom weggenommen gehabt? Soll auch manchmal helfen.
Hast du Kabelinternet oder DSL? Wenn ersteres: Schließ mal einen Computer direkt per Ethernet an das Kabelmodem (da, wo das Kabel von der Fritzbox angeschlossen ist). Damit ließe sich die Fritzbox als Fehlerquelle komplett ausklammern. Ähm ja. Ich lese gerade, dass du DSL hast, also hat sich das erledigt. Ich vermute mal, deine Fritzbox ist nicht an ein DSL-Modem angeschlossen, sondern direkt an den Splitter (kleine weiße Dose mit mehreren Telefonsteckerbuchsen dran, wenn ich mich nicht irre)? Sonst das gleiche ausprobieren: PC direkt ans Modem klemmen.
Was bliebe noch? Ich würde einfach mal darauf tippen, dass die Telekom eine Störung hat oder du zu weit weg vom nächsten Verteiler wohnst und daher die wenigen verfügbaren Kapazitäten in deiner Straße / wie auch immer

einfach ausgelastet sind ("Hauptinternetverkehrszeit" ist ja meist Abends. Meine Oma hat da - wohnt am Ortsrand - auch immer Probleme mit dem Internet...).
Ansonsten mach mal einen Speedtest deiner Wahl, zum Bleistift bei
www.wieistmeineip.de oder (dann kannst du uns das Ergebnis als Bild idealerweise gleich hier verlinken) bei
www.speedtest.net - dabei nicht vergessen, alle anderen, die dein Internet benutzen "rauszukicken", denn wenn jemand nebenbei Youtube schaut oder nur Mails checkt oder ein Mailprogramm nebenbei laufen hat, kann das ganze die Testergebnisse schon verfälschen. Auch Internetradios und dergleichen -> aus. ICQ, MSN, XMPP-Clients -> aus. BitTorrent-Client, Skype und alle anderen P2P Anwendungen -> aus

Dann erst Speedtest starten und uns die Ergebnisse mitteilen.
@chill: Soweit ich weiß, kann man Fritzboxen über die einfache Eingabe von "fritz.box" in die Browseradresszeile aufrufen

(habe aber auch keine) (vielleicht ist das Menü der Fritzboxen ja tatsächlich benutzerfreundlicher als das anderer Hersteller, aber bei den Oberflächen die ich bisher gesehen habe, würde ich lieber nicht zu viel rumklicken, sonst -> Internet futsch, W-LAN ungesichert oder sonstige Scherze)...
@alroar: Ich habe auch keine Ahnung, was du meinst mit DNS Bug?