I just upgraded to Android 5.0 which made all my contacts' random colours even more prominent.
Is it possible to customize the colour for each contact? For example, if I don't like that Mister Brown got a green background, can I change that, haha?
Go to google messenger app. (The new SMS app from Google) -> go into a conversation with the contact you want to change colors -> press the three dots on top -> pick People & options -> around the end you'll see a small color palette where you can go in and change the color.
It seems that it currently works ONLY for people you texted (only through the messenger app).
I can't find a way to change the color of a contact either, but did find an inconvenient workaround. It's really only useful for a few contacts (I just cared about those on speed dial).
Find a contact with the color you do want, then change the name and number. Then make a new contact for the one whose information you deleted (or switch them). The color will stay the same.
So if I want Mr. Green to be green even though his contact color is blue, I can go find a green contact (say, Bob), change the name, number, and anything else to fit Mr. Green, then make a new entry for Bob.
Mr. Brown is out of luck though, since there is no brown.