Problem: The printing system can break down when the selected printer is connected via apple's bonjour protocol.
Solution: Talk directly to your printer, via HPJetdirect or something similiar.
Reported on: Mac OS X 10.4