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