I have an HP LaserJet P2015dn printer that used to cause me headaches and has been causing trouble for some time now again.
Every now and then, the printer would not print. In fact, I got the impression that print jobs were never even sent to the printer.
An ancient thread on UbuntuForums now brought the solution:
Set the network address to a static IP in the router, printer, and printer configuration in the client operating system!
I had the DHCP setting turned on in the printer. Evidently this was causing problems.