These printers will say "out of paper" when they can't pick up paper.
ie. there's no sensor to detect if there's actually paper in the tray, it just tries to pick up paper and errors if it didn't pick any up.
Most likely the pickup rollers just aren't gripping the paper well enough. You may be able to clean them by reaching in though the front with a damp cloth (isopropyl alcohol works better). If there's a removable piece on the back of the printer then that will give better access to the rollers.