TeX Q & Aでご提案いただいたので、もう少し状況をしぼってテストしてみました。
Fedora 10、ghostscript 8.70、gnuplot CVS版（2009/9/9更新）という環境で

set term postscript eps "GothicBBB-Medium-UniJIS-UTF8-H"
set out "test.eps"
plot sin(x) t "サイン波"

ps2pdf test.eps test.pdf

としてできたPDFファイルは、LinuxのAdobe Readerでは問題なく表示できます。
しかし、Windows上のFoxit Readerで表示しようとするとクラッシュします。
Macでは未確認ですが同様でしょう。また、Gnomeの「ドキュメントビューア」や
xpdfでは日本語が抜けてしまいます。いずれも、日本語を含まないとまったく
問題ありません。

また、Windows上で公式バイナリ（4.2.6）で同様に（GothicBBB-Medium-83pv-RKSJ-Hとして）
epsを作り、gs 8.64のps2pdfでPDFを作成しようとするとGhostscriptがクラッシュします。
しかし、gs 8.70にアップデートするとクラッシュはしません（Foxit Readerでも表示可能）。

ということで、gnuplot + ghostscript等の組み合わせによって起こる問題なのかと思いますが、
日本語（あるいは2バイト文字）でしか起きないので気づかれなかったのでしょうか。

〔ツリー構成〕

【2100】 CVS版 postscript terminalでの日本語使用 2009/9/10(木)02:43 wakakumo (1001) ≪

┣【2101】 re(1):CVS版 postscript terminalでの日本語使用 2009/9/10(木)12:36 竹の (1952)