txt2pdf successfully converts cyrillic koi8-r encoded texts.
In Unix, you just need to install additional russian fonts in koi8-r encoding and slightly tune X configuration. As long as I remember, the only thing you should do is to take one of russian font sets (like ftp://camel.gu.ru/pub/cyrillic_k.tgz), unpack it to some place and add a string like
FontPath [path]to XF86Config, where [path] is a path to unpacked fonts. for example, my XF86Config consists of only 2 FontPath strings:
FontPath /usr/X11R6/lib/X11/fonts/cyr FontPath /usr/X11R6/lib/X11/fonts/misc # created by XFree86 # distributionRussian characters in koi8-r encoding cannot be read under Windows with its cp1251 encoding (and vice versa). In Windows, you should first change your regional settings to to Russia (fonts in cp1251 encoding will be installed automatically)
In Windows NT: Control Panel -> Regional Settings -> Russian
I also recommend to check the checkbox "Set as default locale". I have no Win95/98 machine near my workplace, but the way to change locale for them is similar to WinNT.
Then convert your text file from koi8-r to cp1251
This problem could be easily solved with various converters, such as fromwin/towin programs from d1489 package (ftp://ftp.kiarchive.ru/pub/unix/convert/char/d1489-1.4.tgz).
Probably it's possible to make this conversion also after the PDF creation.
It may be interesting to take a look at the existing converter written in perl: http://www.neystadt.org/cyrillic/