плеер с русскими тегами и Last.FM

Поставь патченную taglib (патч на http://rusxmms.sf.net), после этого большинство плееров научатся определять кодировку тегов (Rhythmbox не будет).

а какие еще будут, помимо амарока?

find -iname '*.mp3' -print0 | xargs -0 mid3iconv -eCP1251 --remove-v1 

# equery b `which mid3iconv`
[ Searching for file(s) /usr/bin/mid3iconv in *... ]
media-libs/mutagen-1.11 (/usr/bin/mid3iconv)

mpd + mpdscribble?