Dear Mike,
I don't know about your specific problem, but long experience makes me very suspicious of any font whose name is simply the name of a language, e.g. "RUSSIAN.TTF", "GREEK.TTF", "HEBREW.TTF" etc.
That's a real alarm-bell. It usually indicates an old 8-bit font dating from before the days of Unicode, often in an encoding that wasn't a standard 8-bit encoding even then. In other words, it probably has the Russian characters where the Latin alphabet should be.
If the text that you're struggling with is in one of those fonts, then changing the Replacement table won't improve things much: at best, you'll just get a load of Latin characters instead of Russian ones.
Such problems have little or nothing to do with LibreOffice. They are caused by having text that was originally made in non-standard fonts. As long as the non-standard fonts are present on the system, the text will appear correctly, but if the text is transferred to a system that only uses standard Unicode fonts (which is a consummation devoutly to be wished), then that text can't be displayed as originally written.
There are work-arounds, but the only real remedy is to convert that text into Unicode. If you're stuck, I have some macros that might help. Unfortunately, they only work in MS Word. 
However, if you send me the text, I'll see if I can convert it.
Best wishes,
Alec McAllister
Multilingual Computing Co-ordinator
I.T. (formerly Information Systems Services)
University of Leeds
Leeds
West Yorkshire
LS2 9JT
t.a.mcallister@leeds.ac.uk
Parkinson Building, Room 240, tel 0113 343 3573
Fairburn House extension, Room 2.08, tel 0113 343 8773
Medieval Unicode Font Initiative: http://folk.uib.no/hnooh/mufi/
Personal Webpage: http://www.personal.leeds.ac.uk/~ecl6tam/