Thema Steckdose:
Für Gewöhnlich haut man ja möglichst viel an Steckerleisten ran, die dann wieder an einer Dose direkt an der Wand dran sind. Wenn es jetzt an der Steckdose in der Wand liegen kann, dann ist es wenig aussagekräftig, wenn man das ganze Ding an ne andere Dose hängt. Aber: Wenn der Router an ner Mehrfachleiste hängt kannst Du mal versuchen, ob der an ner Dose direkt an der Wand auch Ärger macht oder nicht.
Oder: Bei den Fritzboxen mal das Netzgerät checken, vielleicht ists das (Kabelbruch (so stabil sind die Stecker die direkt ans Gerät angeschlossen werden ja nun nich..), oder generell was am Netzgerät). Damit verbunden die Frage: Hast Du bei dem Austauschgerät auch das neue Netzgerät angeschlossen oder nur den neuen Router?
Firmwareupdate wäre ne Möglichkeit - aber dann hätte das Austauschgerät nicht die gleichen Fehler gezeigt.
Ansonsten vielleicht doch mal den Provider (also: den I-Net Provider) anrufen, ob vielleicht was an der Leitung ist (die meisten machen dann ne kurze Ferndiagnose mit nem kleinen Messprogramm, die sehen als recht flott ob was an der Leitung ist oder nicht und haben zT sogar die Möglichkeit kurzfristig was zu optimieren (war mal für einem im Kundenservice, von daher weiß ich das).
Noch ne Möglichkeit: Schau mal nach, ob irgendein Witzbold eingestellt hat, dass nach ner bestimmten Zeit der Router die Verbindung kappen soll (afaik kann man dies bei den meisten Fritzboxen einstellen)
@sheepfreak3: T-Online schickt im Normalfall keine Fritzboxen raus, die haben da eher Speedport, Eumex und dergleichen... (die bei mir bislang aber auch 1a gefunzt haben, vielleicht hatte ich aber auch einfach nur Glück)
und falls echt alle Stricke reißen gibts noch
www.router-forum.de oder
www.routerforum.de (sind tatsächlich zwei verschiedene), da hast Du gute Chancen dass schon mal wer so ein Problem hatte und eine Antwort erhalten hat.