I was able to fix this problem on my system
Hi there. I have a HP OfficeJet 5510 and had the very same problem (all black printing was performed w/ the color cartridges)
I also tryed to print things using grayscale via an applications print properties dialog but that failed for me also. I found that there is a CUPS level Grayscale that did solve the problem for me.
I did the following:
1) start gnome-cups-manager ( available in the menu "System"-->"Administration"-->"Printing" )
2) right click on the printer and open "Properties"
3) On the "Advanced" tab, change "Printout Mode" from
"Normal (Color Cartridge)" to "Normal Grayscale (Black Cartridge)"
(Note: clicking the "Print Test Page" will still look wrong, but print from a different app and you should see black again)
The only catch is: If you want to print in color you need to go back into that settings app and change it back. But I seldom print color anyway so this work-around works for me.
Hope it helps you,