So now that I've already posted mine, I just found this thread.

I've not had any problems with playlist names in emplode (WinXP) nor in the menus on the player (2.0b11). But then I saw Tony's comment about naming a folder and dragging that in to Emplode, not an m3u... and that's exactly what I did. I've not tried any .m3us with cyrillic titles.

BTW, did you write a large cyrillic font? I only have medium and small so far