フォント

Adobeのヘルプでもフォントを埋め込んでいない場合の問題点が書かれています。

また、ヘルプを見ていて思ったのですが、フォント埋め込みをしていない場合、英語OSでPDFをAdobe Readerなどで開いた場合には文字化け（文字が読めない状態）しそうですね。

フォントを埋め込むメリット

使用しているパソコンによって使用できるフォントが異なるため、作成した側が使用したフォントが、ファイルを受け取る側に無い場合があります。フォントが埋め込まれている場合には、受け取り側の環境に関わらず、オリジナル通りのフォントで表示したり、印刷したりすることができます。以下のように、問題を避けるためにPDF 文書にフォントを埋め込むことをお奨めします。

• フォントの置き換えを防ぐ
  PDF 文書 （フォントが埋め込まれていない） に含まれるフォントが、ファイルの受け取り側のコンピュータに存在しない場合、Acrobat では PDF を表示する際に、別のフォントに置き換えて表示します。
  フォントの置き換えでは、元の文字の形状がそのまま保たれるわけではありません。特にスクリプト書体（筆記体）などの特殊な文字では、元の形状を再現するのが難しい場合があり、PDF の作成者の意図とは異なる表示になる可能性があります。
• 文字化けを防ぐ
  日本語のテキストが含まれる PDF を日本語以外の環境で表示する場合、環境によっては文字化けが発生する可能性があります。PDF ファイルにフォントを埋め込んでおくと、ファイルを読むユーザのシステムに同じフォントがインストールされていなくても、PDF を作成した際のフォントで表示されます。また、日本語以外の外国語環境とファイルをやり取りする場合も、受け取り側の環境を気にする必要はありません。
  
  日本語以外の英語環境とのファイルのやり取りについて、詳しくはこちらをご覧ください。
  － 日本語版と英語版のデータの互換性はありますか

フォントを埋め込むメリットは何ですか （Acrobat X）（Adobe）

埋め込みされていない場合は代替フォント表示になりますし、

あくまでも代用フォントですから表示の担保はもともとされていません。

ですから解決するとしたらフォント埋め込みでPDFを作成するくらいしかありません。