When it says it's out of paper, but clearly isn't, see...
http://www.youtube.com/watch?v=IYwVritKMMc

Most of this is silly and tedious.

1. Bounce the printer so that it runs through its set-up sequence.
 
2. To clean the rollers, begin around 3:30. Remove rear access door and wipe each roller from right to left rotating up, allow to dry. Clean rollers deeper inside with moistened feeder rollers. Check rollers on access door. Replace door and try again.
 
3. The next suggestion is to remove the paper catching tray and try feeding a sheet into the printer so that it catches. I used the printer status report to do this.This worked for me. After that, I was able to get my printed document. That this works might indicate it's worth doing #2.
 
4. Someone else offered:
   

   "In case anyone has the same problem in the future... My husband found a wheel near the roller hinge, turned it forward a few turns & the roller lowered back down to where it belonged. A simple enough fix, but after almost 3 hours on the phone, HP TECH SUPPORT refused to tell me how to do it! They wanted me to pay them for the info... [it wasn't in the manual either]"

   Performing #2 would be a good opportunity to look for and try this suggestion, but be gentle and don't go forcing random rollers or wheels to turn that don't seem to want to.