Prova a impostare la codifica dei caratteri dopo mysql_connect
funziona in questo modo:
mysql_query ("set character_set_client='utf8'");
mysql_query ("set character_set_results='utf8'");
mysql_query ("set collation_connection='utf8_general_ci'");