I'm pretty sure I learned that convention. Why would it be intuitive? What's the association between red/remove and green/add?
The bigger point I'd like to make is that any talk of universal connotations of colors is probably wrong unless you've really studied it carefully.
For some history on why red means stop and green means go, see Straight Dope: http://www.straightdope.com/columns/read/437/who-decided-red... Apparently it dates back to early railroads, where red meant stop, green meant caution, and white meant go. They discovered this wasn't failsafe when the red filter fell out, the train saw a white light and crashed. So they moved to green for go.
From http://en.wikipedia.org/wiki/Flag_of_the_Soviet_Union :
> The colour red has always been a positive symbol in the Russian culture. The word red (Russian: красный, krasnyy) is etymologically related with the Russian word for beautiful. This can also be seen in Moscow’s Red Square and the Russian Orthodox festivity, Red Easter.
But the whole point is that code removal shouldn't be associated with being negative and so shouldn't be coloured red.