Если принтер "не-постскрипт", то весь вопрос в русификации Ghostscript'а Надо ему с помощью alias'ов вместо латинских шрифтов впихнуть русские. Подробно эта операция расписывается например в пакете из дистрибутива BlackCat. На вскидку, увы, не помню.
Кстати, и проверять результат можно не распечатывая, а выводя в ps-файл и просматривая его через gv.
