Если у вас MySQL 4.1 и любые проблемы с русскими буквами, то попробуйте в начале вашего скрипта, но после соединения выполнить SQL-запрос
  
 


Где кодировка, та кодировка, в которой у вас данные (или в которой вы хотите их видеть). Например для русской виндовой кодировки (windows-1251) это будет cp1251, для KOI8-R - koi8r, для UTF-8 - utf8 и так далее.


АЛЬТЕРНАТИВНЫЙ ВАРИАНТ 
# The MySQL server
[mysqld]
init-connect="SET NAMES cp1251" 

Я сам мучался с этой проблемой, хотя кодировка везде была прописана и в базе и в ПХП нужная, т.е. utf-8. Скрипты также были в кодировке utf-8 сохранены. Но некоторые буквы неправильно в базу записывались. В частности, русские буквы "а" и "с". 

Команда SET NAMES utf8 меня спасла