Je to presne naopak ako píšeš. Phpmyadmin je v poriadku, ale uložené je to zle.
Jedine čo mu pomôže, je spraviť si malý php skript na konveziu.
1. vytvoriť dva konekty do db, jeden pôvodný, druhý so správne nastaveným charsetom
2. načítať dáta, a uložiť ich naspäť cez druhý konekt
prípadne si sprav duplikát tabuľky, a otestuj si to tam, keď to dobre dopadne, tak len prehodíš tabuľky.