Clients losing connection to network printers

I have a single printer server on a Windows Server 2003 SP2 box.  I have approximately 30 HP printers, 8150's, 9040's, 4000 series.  We have about 350 users, most running XP SP3.  We push the printers out to everyone using GPO's and PusPrinterConnections.exe.  It's worked just fine for a long time.

In the past week, we've had about 7 or 8 that are unable to print to most of their printers.  When you check the printer properties, the port connection is not there.  Most of their printers are the same way, but you can usually find one or two where the port properties are correct and they can print to that printer.  Not everyone is on the same floor, and it's a different printer for each person AFA I can tell.

What they have in common is Event ID 22:

"Failed to ugrade printer settings for printer \\<server\PrinterShareName>,LocalOnly driver C:\WINDOWS\System32\spool\DRIVERS\W32X86\3\<hp dll> error 5."

This is purely an HP printer issue.  

I've re-installed the printer drivers for my HP printers.  I've removed printers on the client side and rebooted to see if a re-install would work.  I've restarted the Printer Spooler on my print server, and rebooted it.  Nothing has worked so far.

I've seen lots of postings with no good answers.  Tonight I plan to remove all HP drivers and printers from print server and re-install the whole thing.  I'm hoping someone has a better idea before I do this.  

Thanks for any advice!!