Server OS? Service Pack Level?
Do the same symptons appear on the clients when directly connected to the printer as TCPIP printers, instead of mapped printers?
What type of HP printers? We have had numerous problems with the 2200DNs and have reverted back to the Laserjet4 driver.
The laserjet 4 driver is the most basic as stated by some of my HP reps, and any HP printer can use this driver. Switch it around to see if that helps.
Event logs show anything?