The official HP site says to clean BOTH your Cartridge chip AND your printer chip connections with earbuds dipped in water, with the water pressed out so that it is damp. This made the most sense to me, but did not resolve my problem. Turn your printer off before you do this.
So far, none of the Printer Reset methods have worked for me. Even keeping it off for 10+ minutes.
I've also seen suggestions to first put back your old cartridge and then your new one again, as your printer could still be storing data of your old cartridge.
Faulty New Cartridge
As @Lise said - she just bought bad cartridges and the 3rd one worked. I expect that to be my problem, but if someone has any other things to try, please let me know.