I have problem with view russian names of files in rhythmbox.

It has to do with the encoding of the tag, an example from my collection:

Вирус - Мой герой
Одна минута

Shows up as:
Îäíà ìèíóòà

Because of being encoded in Windows-1251(yours could also be KOI8-R) character encoding instead of UTF8.
You can use a program such as Easytag to change the encoding into UTF8.
The only issue with this is with some portable music players not understanding UTF8 tags, though I'm not sure how widespread this is.

Best Regards,
Williamts99

Yes, possible to rename all track and change all tags, but I'm Russian, and my music collection more than 3 000 tracks with Russian tags. Rename all tracks and tags - is too big work :)

Well that's a whole lot more russian tracks then I have :-) only ~1000 here. But either way, you don't have to rename them by yourself, it can all be done to all of your tracks with just a few clicks(or one command), all it is doing is changing the encoding.

Best Regards,
Williamts99

If that is a problem, why radio stations like Наше Радио have same problem http://i.imgur.com/a13Tv.png.

And I think this problem does not happen with other media players, which only means that this is a bug in Rhytmbox, isn't it?

Any update on this?

Here is what I found http://askubuntu.com/questions/139075/cyrillic-characters-show-as-gibberish-in-rhythmbox

The related bug #992154 fixed it for me. But there might still be a problem with the tags for some, as the question suggests.