FWIW, I've been having the same problem with an HP LaserJet 400 colour M451dn printer. Here is how I solved it:|
In System Preferences Print & Fax, delete any and all references to the offending HP printer.
Then add a new printer - select IP as the method not Default, Fax or Windows. Enter the printer IP address into the Address box. Enter your preferred name into the Name box. The printer driver will now probbaly have picked a Print Using option that matches your printer. Don't accept this option, instead select Generic PostScipt Printer. Now finally hit the Add button.
On system 10.6 and higher you are then asked if there is a Duplex unit or other options - answer correctly. You are now good to go and the printer will be fast and responsive.
On system 10.5 and lower you will in the first instance not be able to print using the duplex unit. However the printer will be fast and resposive. To establish duplex printing, delete the printer (I know I didn't want to do this either). Then add a new printer as described above, but this time let the software automatically select an appropriate option for the Print Using option. You will then be asked about duplex units and you are good to go. Somehow this double cycle of creating a reference to the printer seems to do the job.
I don't know if each and every step is essential, but it has worked on 5 Macs in my office all of which were previously taking very long time (hours) to print documents.