Printers on the network

[Bart Silverstrim]

Occasionally I try printing a PDF and it appears to get "stuck" in the 
queue, processing for 10, 20, 30 minutes or more, and then a 
notification balloon appears in my top panel bar with the printer icon 
telling me that the printer may be disconnected from the network or not 
connected.

The printer still pings on the network, and it's happened with a couple 
printers (although the most recent was using an HP LJ5000). I suspect 
something has gone wrong with the rendering of the print job, but I'm 
not finding the stuck process.

I tried "sudo /etc/init.d/cups restart", no error, but still won't print.

Anyone else have a workaround or fix for this? Or even experience it? 
Seems like a restart fixes the problem (and I'm doing a batch of 
upgrades at the moment so I have to restart now anyway) but insight as 
to what is happening would be appreciated.