Make sure you didn't disturb the black cartridge when you replaced the cyan. I did that once. Just take the black cartridge out and put it back in again.
Or, did you (by any chance) get the black cartridge from 7day shop? If so, I have found the same problem with their cartridges. It gets half way through and then packs up. As it only cost me 99p though I just replace it anyway.