Do the cartridge cleaning thing (from tools menu on printer) at least 5 times or more. It worked for me on about the 9th try with a new cartridge from an HP 3 pack from Costco.
open