Schau mal nach, was in /var/log/cups/error_log steht. Das könnte genaueren Aufschluss geben.
Auch mal Okular aus dem Terminal starten. Vielleicht gibt es da eine aussagekräftige Meldung.
Andere Anwendungen (z.B. Gimp oder anderer PDF Betrachter) drucken die PDFs?