今となって懐かしい話だが、記憶のあるウチに書き留めておきっます。
「MySqlの文字化け」と検索すると沢山の記事が引っかかると思います。

文字化けはMysqlのバージョンによって大きく異なります。
例えばVer4.0では何事も無くSJISを使っていられたのに、Ver4.1にした途端にいきなり文字化けと云った現象が起こります。　たかが4.04.1へのバージョンアップが命取りになります。
極端な話をすればMysql4.0とMysql4.1は別の物と考えた方が良いでしょう。
結論を言えば、SJISは日本独自の文字コードであり国際コードとしては扱われなって置き去りにされた常態です。　根本的にはマルチバイト対応におけるデータベースシステムのバグ（文字コードの誤認識）なのでしょうが、今更急に流れが変わるわけでも無いので、対応策のみまとめておきます。

対策
簡単に云えばSJISを使わずに全てUTF-8に文字コードを統一してしまうことです。
対策my.ini(my.cnf)に次のように追加
[mysqld]
skip-character-set-client-handshake　　←文字コードの自動判別を実施しないようにする
（正確にはMySQL バージョン 4.1.15 以降）

対策デフォルトキャラセットを全てUTF-8にする
default-character-set=utf8

結局、サイトの中の文字コードを全てUTF-8に統一してしまうと云う事です。
携帯サイトなどの都合でどうしてもSJISが必用な場合にはmb_convert_encodingでSJISに変換して表示する。

教訓・・・
新しいものが全ての面で優れているとは限らない。（勿論、優れている点の方が多いですが・・・）