HP Laser Jet 4250, 4350 and the evil PDF

We have been going around and around with this issue. It was mentioned in a previous topic, somewhat addressed, then dropped. Several PDF files will not print on an HP 4250 and 4350 via Preview. The Printer halts with a 49.0E00 Service Error and needs to be restarted. We have updated the firmware and drivers to the newest on HP's website to no avail. I've tried GIMP-print and changing the Printer Description to the '00 Series printer driver (4250 to 4200 Series and 4350 to 4300 Series) and we still get the same Error. Some files will print via Acrobat Reader or Acrobat Professional, but not all. We have even tried to print from OS 10.3.9 and various OS 10.4 renditions. HP support is seems lost on the issue. I can post one of the files that cause this issue to my website, if anyone would like to see it. The same file on Windows prints fine.

Any ideas?