Hi,
Are you sure the paper is in correctly? If it has a paper tray (as opposed to going in from the top) make sure that the tray is all the way in?
Check the lights on the front of the actual printer. With HP printers you tend to have two red light above two buttons. These are the paper and cartridge buttons. If there is a paper error then there will probably be a flashing red light above the corresponding paper button. It may just be a case of pressing that button to signify new paper is in.
If that doesn't work then check the contents of the spool folder (in system32 or Windows folder, i'm not sure, depending on your Op Sys.). Remove any shadow files as well as the accompanying files (maybe in a "Printers" directory inside spool). Now restart your computer and power off and on your printer.
HTH
RayWilson