OK、実際にレコードをフェッチする前に、次のクエリを実行してみてください。
mysql_query("SET NAMES 'utf8'");
mysql_query("SET character_set_results = 'utf8', character_set_client = 'utf8', character_set_connection = 'utf8', character_set_database = 'utf8', character_set_server = 'utf8'");
その後、クエリの実行に進みます。もちろん、上記のクエリは、現在のデータベース接続に関連している必要があります。