I'm assuming you're on WLM.
On the contact list, there should be an icon of a paintbrush on a bar just below your dp, name, pm etc. click it and choose the colour of your choice. It should also apply a lighter shade of that colour to the convo window, but you can change that too, with the same icon in the convo window