Geräte, welche sich über 5GHz WLAN verbinden konnten, hatten kein Problem, es war nur die 2,4GHz-WLAN-Verbindung gestört, der Router meldet in seinen Konfigurationen jedoch keinerlei Probleme.
Nach Recherchen im Netz fand ich heraus, dass dieses Problem tatsächlich des öfteren bei diesem Typ von Router auftritt. Viele Tipps wurden ausprobiert, doch nichts half.
In diesem Beitrag wurde mein Problem genau beschrieben, die Lösung wurde dort jedoch nicht gefunden:
http://www.giga.de/unternehmen/avm/tipps/fritzbox-7490-wlan-probleme-ursache-und-loesung-fuer-verbindungsabbrueche/
Dann fand ich einen Hinweis, dass es mit dem USB3-Mode zu tun haben könnte und mir fiel ein, dass es zeitlich ungefähr hinkommen könnte, dass ich einen USB-3-Stick angeschossen habe und daraufhin die Konfiguration von USB-2 auf USB-3 umgestellt hatte.
Lösung: Nachdem ich im Router wieder auf USB-2 umgestellt hatte, war alles wieder in Ordnung.
Klingt komisch - ist aber so

So hoffe ich einigen der Nutzer einer FritzBox mit W-LAN-Problemen helfen zu können.