Ok, one other suggestion. Have you tried a Cold Reset. Now, I don't mean by powering off the printer. A Cold Reset returns the printer back to its factory settings. I have had printer that although they showed they accepted my changes, the printer acted as if it hadn't. In fact, the printer was a 4000/4050 and was doing exactly what yours is doing.
Here's what you do. I'll assume you have your network card setup for printing via your network. If this is true, you need to remove the network card before performing the cold reset, or the JetDirect will also get reset to factory settings, and you'll need to reset that up again. Anyways. Turn the printer off. Remove the network card(JetDirect). Hold down the "Go" button (green) and while you are holding it down, turn on the printer. When the control panel reads "Cold Reset" you can release the button. Once the printer comes to "Ready" turn it off. Reinstall the JetDirect card, and turn your printer on. Test it. I can tell you that once I did a cold reset, the 4000/4050 I was working on, it allowed paper to feed from tray 2.
Note: This cold reset is also good for resetting the JetDirect card in case some setting gets fowled up with it. And it will work on all HP's with the 4000's style control panel. Which include the 4000/4050/4100, 4500/4550, 5000/5100 8000/8100/8150, 8500/8550, etc....
Timothy N. Couch
A1 Printech
Anchorage, AK