Frezot, если используешь амарок 1.4, то например для *бунты есть вот такое решение. Ну и для других дистрибутивов соответственно смотреть здесь.
Если амарок 2, то перекодировать. Например гуглить на тему tag2utf.py. Или easytag.
Про другие проигрыватели не знаю, не пользовался.