Yes, the idea is to differentiate them. So that once you get used to the different colors/shades, you wouldn't have to actually read the labels.
But I don't think red would be appropriate.
If we go with the basic traffic light psychology, the idea of the "new" label is to signal "go there" to check out the new content. Red would be the opposite of that. So marking something new with a red label would probably not be a good idea, especially if the other new label would be green.
I'll try to use bold or italic for one of the labels. Maybe that will do the trick.