У меня возникла данная проблема с переходом на более новую версию PHP MyAdmin (2.9.0.2). Версия MySql - 4.1.21.
Преамбула:
Сервер удаленный (хостерский), поэтому менять настройки по своему желанию не могу.
PhpMyAdmin тоже хостерский, следовательно вносить изменения в настройки тоже не могу 
Вывод запроса:
show variables like'character%';
character_set_client utf8
character_set_connection latin1
character_set_database latin1
character_set_results utf8
character_set_server latin1
character_set_system utf8
character_sets_dir /usr/share/mysql/charsets/
Решение:
Проблему решил следующим образом
1. В PhpMyAdmin открыл главную страницу и выбрал
"Сопоставление соединения с MySQL" = cp1251_bin
После этого в выводе запроса show variables like'character%' изменилась одна строка:
character_set_connection cp1251
2. При создании таблиц нужно обязательно (!!!) указывать сравнение = cp1251_bin (это для виндозной кодировки, для юниховой - kio8r_bin, но оно должно соответствовать тому, что поставили в п. 1), т.к. по умолчанию создается сравнение по настройкам сервера (в нашем случае явно не русское ;( )
3. Сразу после коннекта к БД в скриптах php нужно выполнить команду 'set names cp1251' (ну или ... koi8r). Обычно коннект к базе выполняется один раз в функции вида
function connect_db(){
$conn = @mysql_connect("localhost", "user1", "password1");
if($conn){
if(mysql_select_db("my_db") and mysql_query("set names 'cp1251'", $conn))
return $conn;
else return false;
} else return false;
}
Так что и изменение нужно внести один раз в данную фукнцию, а затем вызывать ее где надо. Обычно вызов этой функции осуществляется один раз в начале выполнения главного скрипта (см. "модульное программирование" )
Мне этого хватило, но, можно еще добавить команду mysql_query("set character set cp1251", $conn);
p.s. Кстати, если вы сохраняли данные в кодировке cp1251 можно их прочитать в koi8 (!!!) для этого нужно указать соответсвующие кодировки в скрипте подключения к БД, ну и в html конечно 
, правда в этом случае нужно чтобы и весть контент выводился в соответствующей кодировке. Эта удобно использовать если все тексты находятся в mysql.
Удачи!
