I have recently changed over to CUPS in my Debian system although I don't think that caused the problem.
I have an HP Colour LaserJet 4500 which will happily print a test page from the printer menu which includes colour so no problem there.
However in the CUPS setup the only options I get are 'Grayscale' or 'Inverted Grayscale'. The driver selected is 'HP Color LaserJet 4500 - CUPS+Gutenprint v5.2.3 (en)' and the printer will print only in monochrome.
Any ideas?