The big problem is that there isn't just one Russian/cyrillic encoding - there are three main ones (UTF8, KOI8R and Win-CP1251 I believe). I've got my system set up to display Russian UTF8, so when I stick in a Russian MP3 disc and try to use XMMS, I get a lot of ????s. This is because the discs are meant for Windows, which uses CP1251 encoding.
I gave up on XMMS long ago and have used Quod Libet. It has a plugin that allows you to very easily retag the mp3s with UTF8. BMPx works, as well, but lacks the tag editing capabilities.