Intente establecer la codificación de caracteres después de mysql_connect
funcionar así:
mysql_query ("set character_set_client='utf8'");
mysql_query ("set character_set_results='utf8'");
mysql_query ("set collation_connection='utf8_general_ci'");