cD-r0m rašė:
> Susitvarkiau pačiam faile, bet visgi jei mintį turi, būtų įdomu
> sužinot kaip komanda atrodytu..

Komanda taip ir atrodytų. Nežinau, kodėl phpMyAdmin nepatinka, nes 
konsolėje tai veikia (bent jau MySQL v5.5, o turėtų veikti jau nuo 
seniausiai). Tavo atveju panašu, kad įvyko tokia migracija-mutacija:
utf8 as cp1257 -> cp1257 to utf-8

ir 'ĄČĘĖĮŠŲŪŽ_ąčęėįšųūž', utf-8: 0x {
   Ą     Č     Ę     Ė     Į     Š     Ų     Ū     Ž     _  	
   C484, C48C, C498, C496, C4AE, C5A0, C5B2, C5AA, C5BD, 5F,

   ą     č     ę     ė     į     š     ų     ū     ž
   C485, C48D, C499, C497, C4AF, C5A1, C5B3, C5AB, C5BE
}


virto 'ĄČĘĖĮŠŲÅŖŽ_ąĨęėÄÆÅ?ųūž', cp1257: 0x {

   Ä  „   Ä  ?   Ä  ?   Ä  –   Ä  ®   Å  ?   Å  ²   Å  Ŗ   Å  ½   _
   C4,84, C4,8C, C4,98, C4,96, C4,AE, C5,A0, C5,B2, C5,AA, C5,BD, 5F,

   Ä  …   Ä  ¨   Ä  ™   Ä  —   Ä  Æ   Å  ?   Å  ³   Å  «   Å  ¾
   C4,85, C4,8D, C4,99, C4,97, C4,AF, C5,A1, C5,B3, C5,AB, C5,BE

}

Ten, kur klaustukai, tai simbolių kodai apskritai neapibrėžti (ar 
neatvaizduojami) ir tai jau ženklas, kad ne visos raidės 
nenuostolingai/tvarkingai galėjo būti konvertuotos (skaityti toliau).

Taigi, iki šio momento spėju, kad būtent taip atrodė senoji DB (tokiais 
kodais buvo įrašomos reikšmės, o grąžinant atgal jos būdavo 
reinterpretuojamos utf-8 koduotėje kliento pusėje ir įgydavo teisingą 
pavidalą). Kol kas jokios konversijos neįvyksta: db „mano“, kad duomenys 
yra cp1257 koduotės, nors iš tikrųjų jie yra utf-8 koduotės, tačiau kol 
klientas sako ('SET NAMES cp1257' ir pan.), kad jam reikia cp1257 
duomenų, tai db duomenų neperkonvertuoja ir grąžina juos klientui 
tokius, kokie buvo įrašyti. MySQL klientas gavęs duomenis juos atiduoda 
išorei (php), o ten jau jie interpretuojami utf-8 koduotėje ir įgyja 
teisingą pavidalą.

Toliau antroji dalis. Konvertuojant į naująją DB, panašu, jog duomenys 
buvo interpretuoti esantys cp1257 koduotės (nes db taip „manė“; gal 
lentelės/stulpelių charset'as buvo toks nustatytas) ir *konvertuoti* į 
utf-8. Blogai yra tai, kad tie anksčiau minėti simboliai-klaustukai 
negali būti konvertuoti į utf-8, nes jie tiesiog neapibrėžti ir 
pradinėje koduotėje (tad neturi atitikmenų ir utf-8). Kaip 
(nestandartiškai) elgiasi MySQL'as tokioje situacijoje — neaišku: gal 
įterpia kokius klaustukus, jau minėtą NBSP, gal ignoruoja, maišo 
simbolius kodus iš kitų koduočių (pvz latin1). iconv() mėto klaidas, o 
konversijos (cp1257->utf-8) rezultatas, ignoruojant tokius 
neapibrėžtus/klaidingus simbolius, atrodo taip:
cp1257: 'ĄČĘĖĮŠŲÅŖŽ_ąĨęėÄÆÅ?ųūž' pavirto
utf-8 : 'ĄČĘĖĮŠŲÅŖŽ_ąĨęėÄÆÅųūž':

'ĄČĘĖĮŠŲÅŖŽ_ąĨęėÄÆÅ?ųūž', utf-8: 0x {

   Ä     „       Ä     Ä     Ä     –       Ä     ®     Å
   C384, E2809E, C384, C384, C384, E28093, C384, C2AE, C385,

   NBSP  Å     ²     Å     Ŗ     Å     ½     _
   C2A0, C385, C2B2, C385, C596, C385, C2BD, 5F,

   Ä     …       Ä     ¨     Ä     ™       Ä     —       Ä
   C384, E280A6, C384, C2A8, C384, E284A2, C384, E28094, C384,

   Æ     Å     Å     ³     Å     «     Å     ¾
   C386, C385, C385, C2B3, C385, C2AB, C385, C2BE

}

Taigi, galima būtų numanyti, kad raidės virto tokiomis krengelių sekomis 
(atitikmenimis):

Ą - 'Ä„'      (0x: C384, E2809E)
Č - 'Ä*'      (0x: C384) ** (tikrink db ar tik neprikaitaliojai Č <-> Ę)
Ę - 'Ä*'      (0x: C384) ** (tikrink db ar tik neprikaitaliojai Č <-> Ę)
Ė - 'Ä–'      (0x: C384, E28093)
Į - 'Ä®'      (0x: C384, C2AE)
Š - 'Å{NBSP}' (0x: C385, C2A0)
Ų - 'Ų'      (0x: C385, C2B2)
Ū - 'ÅŖ'      (0x: C385, C596)
Ž - 'Ž'      (0x: C385, C2BD)

ą - 'Ä…'      (0x: C384, E280A6)
č - 'Ĩ'      (0x: C384, C2A8)
ę - 'Ä™'      (0x: C384, E284A2)
ė - 'Ä—'      (0x: C384, E28094)
į - 'ÄÆ'      (0x: C384, C386) * — neatitikimas tavo lentelei
š - 'Å*'      (0x: C385)       * - neatitikimas tavo lentelei
ų - 'ų'      (0x: C385, C2B3)
ū - 'Å«'      (0x: C385, C2AB)
ž - 'ž'      (0x: C385, C2BE)

Jeigu mano spėjimas teisingas, tai dar paieškok savo replace() klaidų, o 
su 'Š' didžiąja turėtų veikti tokia komanda:

update customer_address_entity_text set value = replace(value, 
x'C385C2A0','Š');