а вообще, на будущее - указывай что за программу ты используешь Текстовых редакторов полно, никто по кофейной гуще гадать не будет, тебя просто пошлют читать это (не помешает, кстати): http://segfault.kiev.ua/smart-questions-ru.html
Либо перекодируй теги, либо в настройках твоего плеера укажи, что теги в кодировке cp1251, например audacious это позволяет сделать и ничего перекодировать не нужно будет.
Rio Karma не понимал. Да и вообще совневаюсь, что хоть один сможет одновременно отображать нормально украинские и русские названия, если они не в UTF-8.
раньше в линуксе с кодировками все было еще хуже. никакого utf8, никакой локализации, никаких русских шрифтов. все нужно было доустанавливать и донастраивать вручную. а потом когда появилась поддержка utf8-локали — приходилось запускать аццкие скрипты для преобразования имен файлов.