Para usuários do Ubuntu 14.04 (e talvez outros) você não pode adicionar os filtros foomatic como sugerido acima, pois eles entram em conflito com a versão do projeto CUPS (cups-filters).
A dica pode estar em /var/log/cups/error_log
. No meu caso, a saída se parece com isso
[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
Pode ser resolvido com:
sudo apt-get install hpijs-ppds printer-driver-hpijs
Não tenho certeza se ambos são necessários, eu escolhi todas as coisas parecidas com hpijs no Aptitude.