I've noticed a few times on mine, that the little switch / sensor sticks in place (gummed up with ink I suspect)
Basically, when you pull the tray out, it should "detect" the tray being out or missing, then when you put it back, it asks "new or old?"
What tipped me off, is that it didn't indicate when I removed it, that the tray was indeed out.
Just reached in with a ruler, gave the switch a tap (on the top-right hand side, at the back of the slot) the thingy popped out (technical term there
) and all was well.
Mine's a Valuejet 1204 just to be clear on models too.