@gollum,
Depends on the printer but here are a few things to look at.
1) Does the printer have multiple input trays? If the printer is looking for paper from tray two and you have paper in tray one, you will get "out of paper". Look for a "feed" switch or button on the front of the printer. Most multi-function printers have the option to feed from different sources.
2) Maybe the feed tray is not making the contact switch. Unload the paper and reload it making sure it is all the way back in the tray.
3) Remove the paper and add different paper. It could be the top page you have in there has a crease or bend and is not making the switch.