Though other locales may work, the only thing that I have found that works is to start Mozilla in a Japanese locale. Either ja_JP or ja_JP.UTF-8 will do. I normally use en_US.UTF-8 as my locale, and this does not work.
LC_ALL=ja_JP mozilla-firebird
The symptom if you do not do this is that the Postscript contains no errors but blank squares are output instead of all of the Japanese characters.
Also, it may be necesary to manually select one of the two Japanese TrueType fonts in Mozilla before printing (Kochi Gothic or Kochi Mincho).
If you get the following error:
Error: /undefinedresource in --findresource-- Operand stack: Ryumin-Light-EUC-H Font Ryumin-Light-EUC-H (Ryumin-Light-EUC-H) 12 Ryumin-Light EUC-H EUC-H --dict:0/10(G)-- Ryumin-Light false Ryumin-Light Ryumin-Light CIDFont --nostringval-- CMap CIDFont CMap CIDFont
then you will need to use an alternate ghostscript from the gs-esp package. Follow these instructions.