We've seen this at work, and it was a driver issue. We would change drivers, and it would work fine. What I can't remember is whether we had to go from using a generic HP Laserjet 4 driver to the specific printer's driver, or vice-versa (some of our workstations had to use laserjet 4 drivers for other model printer, for quirky applications)
I would suggest upgrading to the latest version of that model's driver first, and see if that corrects it.
As for why it would all of sudden start doing this, I have no idea (never figured out why at work, either)