I was having trouble printing to my HP Deskjet 1000. When printing a test page, the print job would appear to work, without any error message in /var/log/cups/error_log . however, nothing would print from the printer.
Turned out to be a simple solution, I had to install hplip and hpijs
yum install hplip hpijs
apt-get install hplip hpijs
With more recent versions of Ubuntu (and likely Debian), hpijs is now printer-driver-hpijs
apt-get install hplip printer-driver-hpijs
Odd that the (graphical) system configuration tool did not suggest installing those drivers.