This seems very odd. The ink cartridges in most HP printers are complete units with the print head incorporated into the cartridge therefore there should be no crossover or contamination after a cartridge is changed. I could understand if it were an Epson as those cartridges are just ink tanks with all the workings as part of the printer.
Is the replacement cartridge new and genuine? or is is a refilled/compatible one?