MySQL4.1以降では文字セット(charset)をテーブルやカラム単位で設定できるのですが、このバージョンアップで、PHPによる文字セット処理がうまく動かなくなって文字化けすることがあります。 それで、my.confなどでcharasetをutf8に統一することもできますが、他のDBとの都合上、そうもいかない場合、クライアントがDB接続するたびに、文字セットを指定するとうまくいきます。

たとえば、UTF-8の場合

$conn = mysql_connect("host","user","pass");
$rtn = mysql_query("SET NAMES utf8",$conn);

などとしてやるとうまくいきます。