I have been running a greasemonkey script by Mihai Parparita for Gmail to add colors to your labels. It has not been working correctly, so I disabled the script, but I am still getting colored labels (although a bit different style).

Go to your settings, labels, and add #red or #blue or other color after a label name. (ex. Work #blue) and see if you get colored labels.

Not working for me (tried with #green)... have you tried to disable Greasemonkey?

However I don't think that Google implements label colors that way (by adding a string to the label) it's not too user-friendly, they will probably will add an ajax popup with a shiny color palette :)

No joy for me either. Tried capitalized and non-capitalized letters.

Nothing for me. I've got the script running at home but not at work. My labels are still plain here at work.

don´t works for me also.

Hmmmmmm,

I'll try deleting the script entirely and see if it goes away.