Changing the driver to Generic/Postscript Level 2 now enables me to print in colour but there are still problems.
I can print from Gimp using Gutenprint but using the non-Gutenprint option takes forever. Printing a small low resolution image seems to take 10 times as long, at least, as with Gutenprint and higher resolution and larger take so long I've given up waiting (40 minutes and still going).
The printer is connected via the internal network and I can see the data being transmitted which it was during that 40 minutes after which I cancelled the job.
At a guess the job is getting sent in a format that the internal rip engine is struggling with. The Rip boards in those 4500's aren't the fastest thing on the planet now (although ISTR we filled one of the machines with RAM when you came to collect it, it is still possible to send something that will have the printer thinking for a very long time)
Have you tried installing the official HP printing support (HPLIP) ?
http://hplipopensource.com/hplip-web/models/color_laserjet/hp_color_laserjet...