We're currently having the exact same problem here as well. Being the main colour printer for our students it is causing a few headaches.
I updated the drivers yesterday to the latest off of the HP website with no luck.
When we set the printer to print directly to the printer as opposed to our print server (server 2003 R2 x64) it works but, as you would know, kids love their borders and images which with publisher turns out enormous file sizes causes major performance problems with the printer, and is in turn not really a viable fix for the problem for us.