Pri spojení s MySQL musíš MySQL serveru (najlepšie hneď po otvorení spojenia) povedať, že mu posielaš dopyty v UTF-8 (viď dokumentácia):
set names 'utf8'Edit: Vstup od používateľa musíš ošetriť pomocou funkcie mysql_real_escape_string.
Edit2: Keď to chceš používať na triedenie podľa abecedy, tak je lepšie na to vyhradiť jeden samostatný stĺpec, nad ktorým bude index (regulárny výraz alebo like bude pomalé, hoci pri 8000 záznamoch by to nemalo byť nič tragické).