Teaching colour coding is almost always hard, because colour codes are almost always arbitrary. That being said, there are a few instances where you can mitigate the problems:
Represent elements on a scale with a colour transition
If users see a transition of brightness, or between two primary colours, they can guess that each colour somehow represents a point on a linear scale. They won't guess which colour is 'high' or 'low', but they will quickly learn the meaning of colour once they're told the meaning of the two 'end' colours.
Repeat the colour coding and expose users to it as much as possible
Should be fairly self-evident, this one, but do try and fit iconography in wherever possible for the greatest chance of communicating the message.
Design legends well
Legends suck, but with colour coding, they're pretty unavoidable. At the very least, you can try and ameliorate them. Ensure legends obviously belong to the diagrams or items they refer to. Ensure icons on legends closely match the elements the point to - try to give icons the same size on both the UI and the legend, and increase the priority of display bugs in the legend space.
Add non-colour cues
Remember, a small but notable minority of users are red-green colourblind. That means they cannot easily differentiate shades of red, yellow and green. Use non-colour labels and text as a backup, but be warned that small shapes and details will be hard to make out against a blue background, thanks to the eye's poor blue acuity.
Finally, I strongly suggest reading Michael Zuschlag's post, 'Breaking the colour code', which provides an excellent introduction to the use of colour in UI.