That will be a mechanical issue, either the paper guides are moving or the level sensor isn't.
When printing to the Workcentre 6505N the printer will stop in the middle of a printing job and tell me to "Load Tray 1" when the tray is already full of paper. Then if I open and close the tray it starts printing from the beginning of the job.