Google Adds Full Gmail Color Customization
On Thursday Google added a new option to the Themes settings section of Gmail (as shown above), "Choose your own colors." To find it, go into Settings, Themes, and it's the last option on the right and down.
While nice, it starts you from scratch. So you can't take a pre-made theme like Candy and customize it. You can change colors for just about any element, though, including the sidebar(s).
It wouldn't surprise us to see them add the ability to have a custom background image later ... just imagine uploading a picture of your baby or pet, eh?
Anyway, you can go wild, and if you totally hose it, you can just Reset the colors to default, or switch to a different theme. So go wild.