Для сортировки поля с украинскими символами collate (сравнение) должно быть utf8_unicode_ci. Например, если у поля collate установлено в utf8_general_ci то поля с первой буквой i будут вначале, перед буквой а (если сортировка по возрастанию).
Один из вариантов исправления этого – сделать экспорт таблицы, добавить нужный collate и импортировать обратно. Например, есть таблица users, правильный вариант команды создания таблицы может быть таким:
CREATE TABLE `users` ( `id` int(11) unsigned NOT NULL auto_increment, `login` varchar(255) NOT NULL, ... ) ENGINE=MyISAM DEFAULT CHARSET=utf8 COLLATE utf8_unicode_ci;
Просмотр текущего значения Collation для таблицы
SHOW FULL COLUMNS FROM table;
Изменение всех текстовых полей для таблицы
ALTER TABLE table CONVERT TO CHARACTER SET utf8 COLLATE utf8_unicode_ci;