Copied from http://qa.mandriva.com/show_bug.cgi?id=32015 :

============
Evolution can colour message summaries depending on lables you choose. This no
longer works reliable -- sometimes it works, but usually not.

How reproducible:
It fails maybe 19 out of 20 times I try it.

Steps to Reproduce:
1. open evolution and select a mailbox, so you see a list of mail messages
2. single-click on a message summary, then right-click on it, choose Label
from the pop-up menu, and then choose, e.g. "Personal" to make it go green
3.It doesn't go green.

This wouldn't be so important if evolution could still reliably colour messages
in INBOX based on mailing list.
============

I personally did not succeeded at all to set a label, neither on IMAP emails or on local ones. No error/warning is displayed in the console.