The best I've found so far is to add the 'Color' button to the toolbar. Not perfect, but better than nothing.
In Mail, go to View-->Customize Toolbar and drag the 'Color' button up to your toolbar. After hitting 'Done' all you have to do is select the message header you wish to apply a color to, hit the new 'Color' button and choose your color. Couldn't be much easier. I wish this was set as default by Apple, oh well.
Hope that helps.