Shared printers not printing

I've had the following problem at different locations using different 2003
Servers, but always seems to be with HP printers.
Connect the printer via IP address on the server and share out from there. I
can print just find from the server (test page or other). However, when a
client connects to the share to print, the print job just sits in the queue
until the print spooler is stopped, then restarted. The print jobs will then
go through. All the workstations can print just fine if I map them to the IP
address, just not through the server share.