Before you attemp to do anything, please read the entire post first
I have had that problem for about a year now, also with an HP printer, but the "solution" is simple. In the "print'' dialog box go to the "Advanced" tab and choose "Normal Grayscale (Black Cartridge)". This will print in Black and White using only your Black cartridge.
There is some problem with HP printers on Linux because this is what is happening: When you attempt to print the document with the default printer settings, all colors and including black are generated using the color cartridge. In other words, the black cartridge is not being used at all. When you change the settings as said above, only the black cartridge is used.
More generally, your (and my) hp printer can not use both cartridges at the same time; it is either the black or the color - and YOU are the one deciding which cartridge to use.
You may try installing HPLIP-GUI from the package manager and see if there are some options that will allow you to use both cartridges simultaneously.