К вопросу "почему" или "где баг". Г-н Ken Sharp достаточно подробно изложил http://bugs.ghostscript.com/show_bug.cgi?id=690935 (http://bugs.ghostscript.com/show_bug.cgi?id=690935). Если кратко, то postscript из openoffice встраивает Й, как некий специальный глиф ".notdef", который обычно используется для отображения неизвестных (в шрифте) символов. При этом, то, что обычно используется для .notdef (пустой прямоугольник) тоже встраивается в postscript, но уже как не специальный, а как обычный символ. После этого всего, в postscript задается такая перекодировка символов, что Й оказывается неизвестной и для отображения используется глиф .notdef, который она самая и есть. Кодировка также настроена на то, чтобы "настоящие" неизвестные символы отображались прямоугольником, но заданным не специальным глифом, а обычным "гражданским".
При этом всем, будут ли отображаться символы .notdef, зависит от утилиты, которая отображает. ghostscript, например, из postscript отображает по-умолчанию, из pdf - если задана опция.
Начиная, с некой, не очень давней версии, в Ubuntu вместе с cups 1.3 идет патч "pdftops-cups-1.4.dpatch". Он меняет преобразователь pdf-postscript с использовавшегося ранее xpdf на pdftops (фронт-энд к библиотеке poppler). Скорее всего, он по-умолчанию не отображает .notdef, а следовательно и Й и др. символы, которым посчастливилось быть заданными описанным в начале образом. Тот, что был ранее скорее всего отображал. В cups 1.4 это изменение есть оригинально, собственно "pdftops-cups-1.4.dpatch" — бэкпорт.
http://forum.ubuntu.ru/index.php?topic=47731.msg570441#msg570441 (http://forum.ubuntu.ru/index.php?topic=47731.msg570441#msg570441)
В новой версии, кстати, всё работает как надо.