Printing issues when using non-HP Ink

Hi everyone,

So, I have an HP Photosmart 6510 printer, and recently installed a re-manufactured ink cartridge. When I try to print a document, the printer job list will show up as usual, it will connect to the printer, and I will get the following message:

This will go on indefinitely, all while the document does not print. I have PCs in the house as well, and those have printed without trouble.

I also attached a screenshot of the above. Has anyone experienced this before?

Any help would be appreciated!