原因

MP3ファイルのメタ情報がUnicodeになっていなかったことが原因でした。
MP3のメタ情報はID3という形式なのですが、ID3がUnicodeに対応するようになったのはv2以降で、ID3v1を使用しているMP3ファイルのメタ情報をそのままUTF-8のデータベースに格納すると文字化けしてしまいます。

なお、ID3v1はファイルの末尾に、ID3v2はファイルの先頭に書かれるため、両方を一つのMP3ファイルに付けることも出来るそうです。UnicodeのID3v2が付いているMP3ファイルで文字化けが起こる場合は、ID3v1も一緒に付いており、そちらを読んでしまっている可能性があります。(僕の場合はそうでした)

対処法

システム側で対処するよりもタグ情報自体を修正してしまった方が取り回しが楽だと思います。
なお、以下の操作でタグ情報を編集していますが、誤ってタグを全消去する可能性などがありますのでバックアップを取っておくことをオススメします。

私はWindowsでMP3tag (v3.12)というフリーソフトを使用してタグの編集をしています。

インストールしたら、編集したいMP3ファイルを右クリック、もしくはディレクトリを右クリックし、MP3tagを起動します。

タグという欄にそのMP3ファイルに書き込まれているタグのバージョンが記載されています。下画像の場合はID3v1とID3v2.3がどちらも書き込まれています。僕の知る限りだとCD音源はこの形になっていることが多いような気がします。

画面上部のツール(O)→オプション(O)から設定画面を開きます。

タグ→Mpegを以下のように設定します。

ID3v2以降はUnicodeに対応していますがUTF-8に対応しているのはv2.4以降からですので、UTF-8にしたい場合はv2.4を選んでください。
また、ID3v1とID3v2が混在しているファイルをv2のみにしたい場合は「削除」の項目でID3v1にチェックを必ず入れてください。

設定が完了したら、タグを編集したいファイルを選ぶ、もしくはCtrl+Aで全てのファイルを選択し、行いたい操作に応じて次のどちらかを行います。

v1タグを削除したい

左上の×ボタンをクリックし、選択した全てのファイルからタグの削除を行います。

以下のようにv1のタグが消えています。

v2.4タグを書き込みたい

左上のフロッピーボタンをクリックし、選択した全てのファイルにv2.4のタグを書き込みます。ID3v1が存在していても無視してID3v2の部分だけを上書きする形になります。ID3v2.4のみにしたい場合はv1タグの削除も合わせて行ってください。

参考

ID3タグ(Wikipedia)