The impression I get around the Internet is that people either love or hate the default brown theme in Ubuntu.
While we all know that this is easily changed, first impressions do count, so I've had this thought. I don't know if this has already been suggested.
Looking at Linux Mint's way of an introduction 'wizard' when the operating system is first used, how about a similar wizard in Ubuntu where a new user can choose from a pre-selection of themes (blue, dark, etc. in a window similar to the background selection pane (or something).
I think this would prevent the derogatory comments that are being made about in places about Ubuntu being brown, and post install wizards of different nature are not uncommon these days (Pardus, etc.).
This reminds me of all the times I installed Slackware and the KDE wizard came up, I was new the GNU/Linux at the time and that whole thing really captured me, it made me feel like I really did have choices instead of being bound to what I would get by default.
Now, I adore the Ubuntu theme, and I ended up not using KDE anymore because too many options drove me crazy, but I can really appreciate the option to choose a different color scheme, decoration and controls from the get-go.