HP Officejet 6110 on Win 7 64bit "Remove & check cartridge" error.
Here is what worked for me. Pulled the black out, shut and let it run/process, pulled the color out, shut and let it run/process, put the black in, let it run/process, put the color in , let it run/process. And it magically worked (got that order from another post.
I will say I had also run a test sheet with an old black cartridge before that and unplugged it before that, but I don't think that did it because I put the black right back in and it still wasn't working. Only the order above did it.