Did you remember to take the tape seal off the new cartridge ?
I removed the hard plastic cover from Walgreens, it did not had a tape seal, since it was recycled.
I tried using Ubuntu Linux and it worked like charm. I am going to re-install the HP software.
Thank you anyway!