Wow, seems like other people wanted this feature in GMail as well. What I’m talking about? Colored labels :D Last night Google updated its free mail service to also let its users define the color of labels. Here you can choose from 12 different color combinations (you can have the color in the fore- or background) to make it easier for you to keep an overview over your inbox.
The only downside? For now you seem to be stuck with these 12 (or actually 24) colors and can’t define your own. No idea why they didn’t include that in the first place but perhaps we’re lucky and it will be added later on.
For more details check out the respective help page.