Перш за все треба визначити чи це лажа від PHP, чи від MySQL, чи зустрічається в обох випадках.
Далі думати, що робити. Імовірно це локаль стоїть неправильна у хостера. Наприклад ru_Ru, коли треба uk-UA
Десь так для PHP:
$arr[]="А";
$arr[]="Ї";
$arr[]="Є";
$arr[]="Б";
$arr[]="Ю";
ksort($arr);
echo "<pre>";
print_r ($arr);
echo "</pre>";
Для MySQL у phpMyAdmin задати запит типу
SELECT * FROM `jos_categories` ORDER BY `title`
Якщо в обох випадках неправильно, то треба хостера чіпати. Хоча. мабуть, його треба все одно чіпати.