ps2ps コマンドで変換した postscript ファイルを印刷してみるとどうでしょう? 日本語PSファイルを jp.ps として % ps2ps jp.ps jp2.ps としてから jp2.ps を印刷すると,うまくいくかもしれません. TeX だけなら dvipdfm で PDF にして,xpdf か Acrobat Reader から 印刷するとできるかもしれません.