Du solltst mal den Mülleimer leeren..
Wenn Du auf dem MP3Player Dateien per Nautilus löschst, werden diese nur in ein "Trashfile" geschrieben, das immernoch auf dem Player ist.. solange wie der Mülleimer also nicht leer ist, ist wirklich kein Platz mehr da.. Mach mal Strg+h wenn Nautilus den Playerinhalt anzeigt, dann solltest Du ein Verzeichnis .Trash-Benutzername finden..