Ich hatte ebenfalls das Problem: "AB-Speicher voll". Und in der Fritzbox-Oberfläche wurde auch der interne Speicher als nahezu voll angezeigt ("56kB von 512MB frei"). Mein Weg zur Lösung:
1. Optional: Über einen PC mit verbundenem Netzlaufwerk (benötigt SMB - nicht mehr in aktuellen int. Firmware-Versionen) die Verzeichnisse im fritz.nas gecheckt. Dabei habe ich ein altes Verzeichnis mit Dateien entdeckt (bei mir "Audio/Radio/ ..."; kann/wird aber bei anderen vermutlich auch andere Dateien/Verzeichnisse sein), die den internen Speicher nahezu vollständig belegten. Löschen war aber mangels Nutzerrechten nicht möglich. Daher muss es Telnet sein ...
(Ergänzung: zum Checken kann man auch FTP nutzen, also: "ftp://fritz.nas" mit Benutzername "ftpuser" und, falls über die Fritzbox-Oberfläche gesetzt, dem Kennwort für diesen Benutzer, sonst Kennwortfeld leer lassen)
2. Mit Telnet (bspw. über Putty) mit der Fritzbox verbinden (ggf. vorher via Telefon einschalten: #96*7* wählen). Benutzer (falls gefragt - je nach Einstellung der Fritzbox): "admin", Passwort wie an der Fritzbox-Oberfläche.
3. Zum Verzeichnis des Dateiservers wechseln: "cd var/media/ftp"
Im "jungfräulichen" Zustand einer Fritzbox gibt es dort wohl nur die Verzeichnisse "FRITZ" und "lost+found" und, sofern ein USB-Speicher angeschlossen ist, auch dafür ein Verzeichnis. Je nach Firmware ober bei aktiviertem Medienserver können aber u.U. weitere Verzeichnisse existieren.
4. Die Verzeichnisse bzw. Dateien prüfen
+ "cd Verzeichnisname" wechselt in das Verzeichnis "Verzeichnisname" (groß/klein beachten!)
+ "ls" zeigt den Inhalt an bzw. "ls -e" eine detaillierte Übersicht inkl. Datum und Größe
+ "cd .." geht eine Verzeichnisebene zurück
+ "rm Dateiname" bzw. "rm -r Verzeichnisname" löscht die Datei bzw. das komplette Verzeichnis mit Inhalt - VORSICHT !!!
Beim Löschen sollten natürlich nur Dateien gelöscht werden, von denen man sicher ist, dass sie entweder dort nicht hingehören oder bspw. alte, nicht mehr benötigte Nachrichten auf dem AB (vermutlich unter "../FRITZ/voicebox/rec"), Bilder für die DECT-Telefone (vermutlich unter "../FRITZ/fonpix"), Klingeltöne (vermutlich unter "../FRITZ/fonring") oder eine alte bzw. zu große Medien-Index-Datei (vermutlich unter "../FRITZ/mediabox") sind
Das ganze kann man parallel über die Fritzbox-Oberfläche verfolgen: "Heimnetz - Speicher (NAS)". Dazu nur "Aktualisieren" und schauen, ob nach dem Löschen mehr Platz frei ist - und irgendwann ist dann auch der AB-Speicher an den Telefonen nicht mehr voll
5. Am Ende Telnet wieder via Telefon ausschalten: #96*8* wählen