holas, con que juego de caracteres creaste tu base de datos y tus tablas, estas seguro que todo esta con el juego de caracteres correcto y su respectivo cotejamiento, por que no revisas con:
Código PHP:
mysql> SHOW CREATE TABLE nombreTabla;
mysql> SHOW CREATE DATABASE nombreBaseDatos;
ahi veras si el juego de caracteres y el cotejamiento esta correcto en las tablas y en la base de datos, saludos, cya