こんばんは、Ykawaです。

説明されている環境で開発を行ったことが無いので、
回答が的を得ていなかもしれません。
その辺りは、ご了承ください。

mySQL側と、PHP側の文字コードに相違があるように感じられます。
mySQL側の文字コードを、下記のSQL文などで確認してみては、如何でしょうか？
そもそも、下記のクエリをPHP経由で実行できるのか分かりませんが

＊対象のテーブルの文字コードを確認してみるとか
　mysql> show table status;
| Name   | Engine | Version | Row_format | Rows | Avg_row_length |
Data_length | Max_data_length  | Index_length | Data_free |
Auto_increment | Create_time         | Update_time         | Check_time
| Collation       | Checksum | Create_options | Comment |
+--------+--------+---------+------------+------+----------------+------
-------+------------------+--------------+-----------+----------------+-
--------------------+---------------------+------------+----------------
-+----------+----------------+---------+
| testaa | MyISAM |      10 | Fixed      |    2 |             13 |
26 | 3659174697238527 |         2048 |         0 |           NULL |
2008-04-07 19:34:42 | 2008-04-07 19:34:42 | NULL       | utf8_general_ci
|     NULL |                |         |

＊システムの環境を除いてみるとか
mysql> status;
--------------
mysql  Ver 14.12 Distrib 5.0.51, for pc-linux-gnu (i686) using readline
5.1
Server characterset:    utf8
Db     characterset:    utf8
Client characterset:    utf8
Conn.  characterset:    utf8