It looks like Gmail is rolling out new features. This time, Colored Labels.
I had seen something like this with a greasemonkey script so it looks like Gmail may be integrating popular third party ideas into Gmail. It sure does make identifying emails easier within labels.
Find out more here.