Update
Der Telekom Techniker war glücklicher Weise ein Bekannter von mir. Er hatte auch keine Ahnung, an was es liegen könnte und hätte eigentlich unverrichteter Dinge wieder abziehen müssen, da das Problem nichts mit der Leitung zu tun hatte. Da er mir aber trotzdem helfen wollte, schlug er vor den neuesten Router "Speedport Smart", den er zufällig dabei hätte, auszuprobieren. Router ausgetauscht und alles funktionierte, als wäre nie was gewesen. Er sagte, dass das Problem evtl. durch ein Update entstanden sein kann, was man im Nachhinein aber nicht mehr überprüfen kann.
Solltet ihr euch also weiterhin mit dem Verbindungsproblem herumschlagen, versucht es mal mit einem anderen Router.