I received the same error on Hardy and Intrepid when using the "HP LaserJet 4000 Series Postscript [en] (recommended)" driver. With Intrepid, changing the driver to "HP LaserJet 4000 series Foomatic/hpijs [en]" resulted in a test print without error.
ii foomatic-db-hpijs 20080915-0ubuntu1 OpenPrinting printer support - database for HPIJS driver
ii hpijs 2.8.7-0ubuntu6 HP Linux Printing and Imaging - gs IJS driver (hpijs)
ii hpijs-ppds 2.8.7-0ubuntu6 HP Linux Printing and Imaging - HPIJS PPD files
ii hplip 2.8.7-0ubuntu6 HP Linux Printing and Imaging System (HPLIP)
ii hplip-data 2.8.7-0ubuntu6 HP Linux Printing and Imaging - data files
ii hplip-gui 2.8.7-0ubuntu6 HP Linux Printing and Imaging - GUI utilities
I received the same error on Hardy and Intrepid when using the "HP LaserJet 4000 Series Postscript [en] (recommended)" driver. With Intrepid, changing the driver to "HP LaserJet 4000 series Foomatic/hpijs [en]" resulted in a test print without error.
ii foomatic-db-hpijs 20080915-0ubuntu1 OpenPrinting printer support - database for HPIJS driver
ii hpijs 2.8.7-0ubuntu6 HP Linux Printing and Imaging - gs IJS driver (hpijs)
ii hpijs-ppds 2.8.7-0ubuntu6 HP Linux Printing and Imaging - HPIJS PPD files
ii hplip 2.8.7-0ubuntu6 HP Linux Printing and Imaging System (HPLIP)
ii hplip-data 2.8.7-0ubuntu6 HP Linux Printing and Imaging - data files
ii hplip-gui 2.8.7-0ubuntu6 HP Linux Printing and Imaging - GUI utilities