I encountered exactly the same problem as HB. I tried to solve it your way and following all instructions including restarting cups and even restarting the machine. It still came out black and white.
Then I tried editing like HB did. That solved my problem. Prints are in color now.
ubuntu@ubuntu:/etc/cups/ppd$ diff /etc/cups/ppd/Color-LaserJet-1600.ppd /etc/cups/ppd/Color-Lase
Forum: HP Color LaserJet 1600