В чем проблема непонятно, вроде перезапуск сервера как выше ДОЛЖЕН изменить кодировку сервера..
И кстати он ее изменил.

Сейчас как я понимаю проблема в том что соединение открывается в latin1, почему затрудняюсь сказать:

| character_set_client     | latin1                     |
| character_set_connection | latin1                     |
| character_set_results    | latin1                     |

Сам с таким не сталкивался, но могу дать рекомендации

1. С mysql.ru FAQ:

Q. Как обеспечить корректную работу MySQL с русскими символами при сортировке и выборке данных?
A. В /etc/my.cnf вписать в блоке [mysqld]: default-character-set=koi8_ru (или cp1251). При работе с базой можно выставить рабочую кодировку через: SET CHARACTER SET koi8_ru

2. C mysql.com Ref.Man:

SET NAMES 'charset_name'
SET CHARACTER SET charset_name

SET NAMES 'cp1251' tells the server “future incoming messages from this client are in character set cp1251.”
или в приблизительном переводе на русский: SET NAMES 'cp1251' сообщает серверу что все последующие входящие сообщения от этого клиента будут приходить в кодировке cp1251

Pheonix, будь я на твоем месте, перекомпилировал бы MySQL с нужной кодировкой по умолчанию, лишние бы отключил. Если сайт русскоязычный и документы в кодировке cp1251, возможно, лучшим вариантом будет использовать именно эту кодировку.

Извините, на этом из обсуждения выпадаю