Das bestätigt meine Theorie. Beim neu Taggen wird sicher standardmäßig der unterstützte Zeichensatz verwendet.
Du bräuchtest jetzt also ein Tool, mit dem du die Tags umcodieren kannst.
Sowas kannst du sicher selbst basteln. Synaptic unter Ubuntu hat einen ganzen Sack voller Programme zum Thema ID3.
Wenn du dir mal die manpages dazu anschaust, findest du sicher eines oder mehrere, womit du ID3-Tags auslesen und in einem definierten Zeichensatz schreiben kannst.
Dann brauchst du dir nur noch ein Script schreiben, dass in einer Schleife über alle deine MP3s läuft, die Tags ausliest und im neuen Zeichensatz wieder zurück schreibt.
Das sollte mit Perl, PHP (CLI) oder einer beliebigen Shell nicht allzu schwierig sein und ist sicher ein nettes Wochenendprojekt.