Для того, чтобы MySQL правильно сортировала и искала по полям с русскими символами, в версиях 3.23.x нужно вписать строку в my.cnf (my.ini под Win32):
default-character-set=cp251
или
default-character-set=koi8-r
(зависит, естественно, от кодировки вашего текста).
Строка должна быть вписана в раздел [mysqld], если его нет - его следует добавить.
*никс:
Файл my.cnf должен находиться в /etc (если при установке не были указаны другие пути)
Win32:
Файл my.ini должен находиться в c:\
После добавления этой строки в my.cnf сервер MySQL следует перезапустить, индексы по текстовым полям пересоздать.
Список всех возможных кодировок и текущую кодировку можно узнать так:
SHOW VARIABLES LIKE 'character_sets'; //список всех поддерживаемых
SHOW VARIABLES LIKE 'character_set'; //текущая кодировка
http://phpclub.ru/talk/showthread.php?s=&threadid=37607&highlight=characterset