Google's thrown in a slight change to Gmail's Themes option. Users can now select their own colors for background, links, tabs, and text.
There's actually a lot of customization available so that the sidebar can be customized separately from the message body, for example. Custom colors are an option, too, which is carried over from Labels. However you decorate your Gmail, you'll be stuck with the multicolored Gmail logo, so theme-obsessed aesthetic ascetics are out of luck.
The feature can be accessed from the lower-right corner of the Themes page, once you've activated Themes in Gmail Labs.