По-моему, стОит проверить, какая кодировка тэгов. Лично я все тэги прописываю в юникоде (utf-8 (16)) и для этой цели использую бесплатную подWindowsкую прогу TagScanner, которая под Wine работает хорошо (ничего лучшего не нашёл в своё время и не жалею об этом). Ну, clementine не пользуюсь, а Qmmp да Rhytmbox отображают русскоязычные тэги в юникоде чётко, в то время, как с кодировкой win 1252 (или как её там) - кракозябры.