Por que no revisas como estan tu codificacion para la conexion, el cliente y tu base de datos, prueba este comando:
mysql> show variables like "c%";
Código:
+--------------------------+----------------------------+
| Variable_name | Value |
+--------------------------+----------------------------+
| character_set_client | utf8 |
| character_set_connection | utf8 |
| character_set_database | utf8 |
| character_set_results | utf8 |
| character_set_server | latin1 |
| character_set_system | utf8 |
| character_sets_dir | /usr/share/mysql/charsets/ |
| collation_connection | utf8_general_ci |
| collation_database | utf8_spanish2_ci |
| collation_server | latin1_swedish_ci |
revisaste directo en mysql si es que la codificacion funciona o solo desde tus paginas php, revisaste la codificacion de tu navegador?.
saludos.., cya