次のことを試してください：
mysqlに接続した後、次のクエリを実行して、UTF8を使用していることを確認します。
mysql_query("SET NAMES 'utf8'");
mysql_query("SET CHARACTER SET 'utf8'");
HTML（ヘッド）で正しいエンコーディングを使用していることを確認してください：
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
これで問題が解決しない場合は、ISO-8859-1
などの別のエンコーディングを試してください。