Red and green has a certain logic to it, in the sense that Western culture does associate green with “positive” states and red with “negative” states. In this sense, red is appropriate for deleted code because it is believed to be less correct than the replaced code (otherwise, it wouldn’t have been deleted; remember the teacher’s red marks on your paper). Deleted code is also negative in the sense that it isn’t run –it’s “stopped,” while the (green) replacement code “goes.” (without the original article I can’t judge the merits of its argument; maybe someone was traumatize by an over-zealous teacher).
However, the accessibility (color-blindness) concerns are legitimate. The usual ways of dealing with this, assuming color coding is the right choice in the first place, is to add a redundant code.
You could, for example, and add strikethrough to make it clear what’s deleted:

However, that also makes the deleted text harder to read, so if the task involves really studying the deleted text, it’s not a good choice.
A common choice is to go with shade coding. With a white background, you can go with a very dark green (okay, almost black) and keep all text minimally legible (and nonpink):

The above shades contrast 3.0 against each other and at least 4.5 with the background, which is the minimum you want, and also about the most you can get.
The deleted text will appear lighter than the replacement text, helpful to not only those who are color blind but also for those who use non-color printouts (the default at my work). It seems sensible for deleted code to be lighter, as if it isn’t there as much as the replacement text.
If for any reason you want to avoid negative/positive connotations, I’d recommend a brown-blue combination:

These have no particular strong associations in Western culture, and blue-yellow color blindness (and total color blindness) is much rarer than red-green, so more people will benefit from the color coding. I also made the deleted code a lighter shade than the replacement to have shade coding too.