2日ほどMySQLの文字化けの件で悩んでおりました。
4.1からの文字化けの問題は有名らしいですね。
手元にこんな本がありましたので参考にしました。

現場で使える MySQL (DB Magazine SELECTION)

現場で使える MySQL (DB Magazine SELECTION)

日本語処理ということで丸々1章使ってます。
日本語処理ってのはこの本の中でももっとも難しい内容であるとのこと。

とにかく文字コードを設定する箇所が多くて、何がなにやら
分かりませんでしたが、この本を読んで少しは理解できたような...
当方の場合の対策としては、クライアントの文字コードを何も設定してなかったので、
これをEUC(ujis)に設定するということ。
phpのpgは全てeucに統一してるので)
具体的には、set names ujis;を最初の方に記述しただけ。