А в постскрипте шрифт точно есть?
Покажите.
вот настройки сохранения .ps файла, а так не нашел как посмотреть сами шрифты в самом .ps файле
а вот настройки Distiller'а, шрифт TimesNewRomanPS-BoldMT имеется, на всякий случай поставил на "Всегда встраивать", итог тот же, в квадраты
если что скинул ps-файл (koalych_ps.rar) в Пример pdf-файлов с "проблемными" изображениями