Wow. What a production.
For anyone with an HP Laserjet 4 Plus or similar, I just got mine working.
Removed old printer from "Printers & Scanners"
Physically unplugged USB connection.
Plugged USB back in.
Added printer with HP LaserJet 4 Plus - CUPS+Gutenprint v5.2.9 driver
Especially for older HP LaserJet I recommend these drivers. Allows options for setting things like amount of printer RAM my LaserJet 4 Plus works great with these drivers, was sluggish with other drivers. No problems with Lion or Mavericks.
Apple 2.10 HP drivers
I had similar issues with my LaserJet 2100M, but this solution will probably work with most networked printers: doing a cold or NVRAM reset. After doing this (procedures vary by model), things were working fine for me again.
Before this, I had reset Mavericks printing services, deleted and set up the printer numerous times, and tried various wired and wireless connections, but the problem persisted. After resetting the printer, all OK, using the generic driver that came with Mavericks.