Zebra is a great customizable theme that allows easy color changes and other customizations right from the Admin panel. It’s been upgraded and released as Zebra 2.1 recently, bringing a fresh look with the same control. Change colors, logos, background images and more through the Admin panel and with FTP access.
I tried it out and used http://www.colorpicker.com/ to edit the colors to my linking. Check it out yourself by downloading it from http://moodle.org/plugins/pluginversions.php?plugin=theme_zebra.
As a bonus, Danny Wahl (theme creator) has built-in some of the responsive design that Stuart highlighted in my previous post (resizing the window changes how the columns display).