My printer is HP CP1215 had also an error: Printer Paused - "/usr/lib/cups/backend/hp failed"
After restarting both
avahi-daemon and identifying printer with
lpstat -p and enabling with
cupsenable, I was able to print again. Restarting only
cups and enabling did not do the trick.
I also changed default policy to retry-job and finally ended up avoiding errors in future with cronjob:
* * * * * lpstat -p |grep "poissa käytöstä" && service avahi-daemon restart; service cups restart; cupsenable HP_Tuloostin
poissa käytöstä is Finnish localization text for maintenance "out of order" and
HP_Tuloostin is name of my printer.
In my experience both default-policy and current printer policies should be configured to be retry-job. Default policy is just policy which you get when you are installing a new printer.