何の解決にもなってませんが、とりあえずこんな感じでした。

virtualboxのubuntu 14.04.1-32bit-remixで試してみました。
libreoffice writerのPDF出力機能で作成したPDFは、pdftotextで正常にテキスト変換されます。
(出力されたPDFはevinceで表示する限り文字化けしていない)
又、インターネット上で適当に見つけたPDFもpdftotextで文字化けせずに変換できました。
しかし、cups-pdfを通して作成されたPDFを変換すると文字化けしました。
(出力されたPDFはevinceで表示する限り文字化けしていない)

# libreoffice writerで以下の内容をPDF出力機能を使ってPDFに出力し、pdftotextで変換する。

[半角]
1234567
abcdefg
ABCDEFG
!"#$%&'

「全角」
１２３４５６７
ａｂｃｄｅｆｇ
ＡＢＣＤＥＦＧ
！”＃＄％＆’
あいうえお
アイウエオ
月火水木金土日

作成されたPDFをevinceで開くと、文字化けも無く正常に表示される。
又、pdftotextで変換しても以下の様に文字化けは発生しない。

$ pdftotext -layout PDFファイル名 -
[半角]
1234567
abcdefg
ABCDEFG
!"#$%&'

「全角」
１２３４５６７
ａｂｃｄｅｆｇ
ＡＢＣＤＥＦＧ
！”＃＄％＆’
あいうえお
アイウエオ
月火水木金土日

# libreoffice writerのPDF出力機能は使わずに、印刷からcups-pdfに出力する。
作成されたPDFをevinceで開くと、文字化けも無く正常に表示される。
しかし、pdftotextで変換すると文字化けする。

$ pdftotext -layout PDFファイル名 -
      !
"#$%&
'()*+
,-./012

# geditに同じ内容を記述して、cups-pdfで出力し、pdftotextで変換する。
文字化けする。(但し、文字化けの仕方は変わる)

$ pdftotext -layout PDFファイル名 -
 ✁✂✄: ☎✆✝✞✟✠✡☛☞ 1   ✌✍✎ 1 / 1
[✏✑]
1234567
abcdefg
ABCDEFG
!"#$%&'

✒✓✑✔
✕✖✗✘✙✚✛
✜✢✣✤✥✦✧
★✩✪✫✬✭✮
✯”✰✱✲✳’
✴✵✶✷✸
✹✺✻✼✽
✾✿❀❁❂❃❄

evinceでPDFを表示する限りは文字化けしていない。
cups-pdfとghostscriptではなくpdftotextの問題の様にも見えますが、cups-pdf経由でない物は文字化けしない結果から、ghostscriptを経由して作成されたPDFに問題がある可能性もあります。
cups-pdf
ghostscript
pdftotext(poppler-utilsパッケージ)
poppler-dataパッケージ(ghostscriptのcmap data)

# 以下のオプションも試してみました。
*cupsFilter: "application/vnd.cups-pdf 0 -"
*cupsFilter: "application/vnd.cups-postscript 100 -"

*cupsFilter: "application/vnd.cups-pdf 0 -"は、生成されるPDFファイル名がPDF.pdfになり、evince上では白紙となる。
*cupsFilter: "application/vnd.cups-postscript 100 -"は、header(タイトル)がフルパスのファイル名になり、ファイル名も受け継がれる。(evince上では正常に表示される)
文字化けする件とは関係なさそうです。

＞katsu07さん
ご回答ありがとうございます。

pdftotext の検証について、cups-pdf が pdftotext 実施後の文字化けに影響がありそうですね…。

申し訳ありません、私の説明不足もあり状況を正しくお伝えすることができていませんでした。
PDFファイルはすでに他のツールを使って生成されている状況で、「各アプリケーションのプリントアイコンをクリックした時や…」というような操作ができない状態です。

実際の動作としましては以下の通りです。

1)とあるツールから cups-pdf を指定して印刷物を生成する（*この際、詳細な印刷設定などは行えず、使用するプリンタを指定するのみ）
2)生成されたPDFファイルを pdftotext でテキストファイル化し、PDFファイル内にある「半角数字」を取得する

そのため、
■1)での cups-pdf の印刷設定
■2)での pdftotext の対処
上記2箇所が文字化けの対処の対象になるかと考えています。

2)についてはkatsu07さんの検証から、pdftotext には問題がないように思います。

1)について、現在再現する環境を構築しているところで、私の方でも検証が行える状況になるかと思います。
引き続き、何かわかりましたらご回答をお願い致します。