I had the same problem as yourself a while back. There are two formats that dictate how your keystrokes are converted into what you see on screen, ANSI and UNICODE. UNICODE can recognise many more characters than the standard ANSI and is used for languages with non-standard characters, Russian and the like. Microsoft Word recognises UNICODE, after calling Quark Tech Support I discovered Quark doesn't!
In the end I set the Russian text in Adobe illustrator (which does support Unicode!) converted a version to outline text and imported it into my Quark doc as an EPS. A little long-winded but it worked!
I have since requested the translation house we use to supply text to us in a format that Quark can use, they charged us a little extra (and wouldn't tell me how they did it) but it worked - if you get your text from a translation house it might be worth asking them.
Hope this is of use!