intenta con esto antes de mandar la consulta
Código:
mysql_query('SET NAMES utf8') or die(mysql_error());
mysql_query('SET CHARACTER SET utf8') or die(mysql_error());
mysql_query('SET COLLATION_CONNECTION="utf8_general_ci" ') or die(mysql_error());
el asunto es que puede que tengas tu BD en utf8, y tus archivos tambien, más no la comunicación entre php y mysql, y lo que hace esto es realizar la conexión o la comunicación en la misma codificación.
Lo mejor para no batallar es poner estas directivas en el archivo de my.cnf en tu servidor, quedarian algo como esto:
Código:
init_connect='SET collation_connection = utf8_general_ci'
init_connect='SET NAMES utf8'
character-set-server=utf8
collation-server=utf8_general_ci
skip-character-set-client-handshake
Esto claro, si tienes acceso al servidor.
Espero te sirva