This is as simple as they come. After a week of trying different things when we got a new HP 5100ntd, we had flaky printing from any number of applications.
After calling HP, the solution was to force the printer to use the HP 5000 Series drivers, as there are serious issues with the 5100 Series drivers for OS X. I was told that HP had no plans yet to address the problem. But hey, if you want to call and complain that wouldn't hurt.
Using the 5000 Series drivers is our only option, and have had no problems at all.
On a technical note, we have had better success with LPD printing with the 5100, even though IPP printing worked fine with our 5000 Series printers.