自分もそれで困ってましたが、easytagで全部直しました(ファイル数多すぎてエラーでまくりで結局ほぼすべて手動で直しましたけど)。タグ自体の文字コード変えなくても、リズムボックスの曲データベースの文字コードを変えるという方法もあったと思います。詳しいことは
rhythmbox 文字化け
でそこそこhitするはずです。

追記:
以下のページが参考になると思います。
rhythmboxのライブラリの文字化け対策-けんけんのFedora Core メモ
上のページに従うと、

1.まずは音楽ファイル群を取り込んで(インポートして)ください。

2.

参照先 による投稿:

そして、エディタで次のコードをファイル名 /bin/convert_rhythmdb.plとして、保存します。

の下に書いあるスクリプト(一連の作業を自動で実行してくれる指示書みたいなものです。perlっていう一種のプログラミング言語で書かれています。多分...)をメモ帳にコピーして ~/ にでも co_rh.pl とか名前つけて保存してください(~ は /home/あなたの名前 を表します)。

3.あとは メニュー => アクセサリ から 端末 を開いて、

chmod +x ~/co_rh.pl

を入力してEnter(ファイルのアクセス権限を変更する命令)

cd ~/.gnome2/rhythmbox

を入力してEnter(~/.gnome2/rhythmbox に移動するという命令)

co_rh.pl < rhythmdb.xml.orig > rhythmdb.xml

を入力してEnter(co_rh.pl に書いてあることに従って rhythmdb.xml の文字コードを変換してくださいという命令。rhythmdb.xml は 1. で取り込んだ曲名のリストです)

...こうすることで、音楽ファイル本体には何も手を加えずRhythmboxの文字化けを解消することができるハズです(ただ、文字化けした音楽ファイルが追加される度にこの作業をしなきゃいけないらしいですけど。でも今後Ubuntu上だけで音楽ファイルを管理するなら以後めったにする作業ではないはず)。
「言われなくても分かってるよ。」って感じだと思いますけど。後々の人の為にも。間違いあったらごめんなさい。

最後の編集者: saks (2008-04-20 21:44:17)

ちょっとおもしろいことが分かったので追伸です。

winamp5.52以降にて新規タグを作成するとunbuntuに持ってきても文字化けしません。
それ以前のwinanpで作ったタグは確実に日本語は文字化けしてました。
winampの内部処理が変わったのかもしれません。 

ウィンとunbuntu双方でデータを使ってる方はお試しください。

プレイヤーがaudaciousならば設定によって変換せずとも文字化けせずにタグ情報を読み込めます。

ただ、根本的に解決するには他の方も書いておられるようにeasytagでタグの文字コードを変換するのが一番良い解かと思います。
そもそもid3v2でShift-JISを使ったタグをつける事が規格に沿っていない不正なタグのようですし。

そもそもこの規格がいい加減だからタグ回りの様々なトラブルが起きているようですが…
以下はうろ覚えですが、unicodeを使うにしてもid3v2 2.2の規格ではUTF-16のみでUTF-8は定義されておらず、2.4ではUTF-8もアリとかそういうのもあったように記憶しています。まさにカオスです。

私はyamaさんが書かれたようにiTunesで一気に変更させました。
変換させたいファイルを選んでID3タグ変換→ID3タグバージョンv2.4　これで全部Ubuntuでも日本語表記出来ています。

walkmanなどのデジタルオーディオプレーヤは、ID3タグをshift_jisで書かないと認識できないようですね・・・。