I'm able to print some PDFs from Preview via AirPrint to an HP Color Laser, but others never do. The ones that fail seem to run through the Print Queue, show they were transferred to the printer, the printer blinks, but then nothing happens.
The only workaround has been to screenshot the PDF, and print from the screenshot image.