Comment 15 for bug 669152

Support for the Phaser 6250DP was added in gutenprint 5.2.6 / Ubuntu 10.10 and probably only grayscale for now.
Before there was no gutenprint driver for this printer, other open source drivers in Ubuntu 10.04 (Foomatic/Postscript, Foomatic/hpijs-pcl5e, Foomatic/ljet4, ...) are only for monochrome output.

Only driver I see that is able to do color is the proprietary Postscript driver from Xerox which you can find here:
http://www.support.xerox.com/support/phaser-6250/file-download/enus.html?operatingSystem=linux&fileLanguage=en_GB&contentId=61334&from=downloads&viewArchived=false
or here:
http://www.openprinting.org/ppd-o-matic.php?driver=Postscript-Xerox&printer=Xerox-Phaser_6250DP&show=1

>There was no problem printing in color in ALL earlier Ubuntu versions starting from 8.04 and including 10.04
What driver did you use in Ubuntu 10.04 that did color? Risk-free testing without installation is possible with the live-cd.