For Ubuntu 14.04 users (and maybe others) you cannot add the foomatic-filters as suggested above, as they conflict with the CUPS project's version (cups-filters).
The hint may be in /var/log/cups/error_log
. In my case, the output looks like this
[17/Aug/2014:12:47:31 +1000] [Job 83] JCL: 12345X@PJL
[17/Aug/2014:12:47:31 +1000] [Job 83] <job data>
[17/Aug/2014:12:47:31 +1000] [Job 83] sh: 1: hpijs: not found
[17/Aug/2014:12:47:31 +1000] [Job 83] GPL Ghostscript 9.10: Can't start ijs server "hpijs"
[17/Aug/2014:12:47:31 +1000] [Job 83] renderer exited with status 1
[17/Aug/2014:12:47:31 +1000] [Job 83] Possible error on renderer command line or PostScript error. Check options.Kid3 exit status: 3
It can be solved with:
sudo apt-get install hpijs-ppds printer-driver-hpijs
Not sure if both are needed, I just picked all hpijs-like things in Aptitude.