Just to have a little fun, I tried reconstructing the Google color scheme. Just to see if I could improve it in only half an hour with a bit of Photoshop magic. Here's what a Google results page looks like, these days:
If I throw our all the details and just concentrate on the blocks of color in the page, then this is what I see:
The current page isn't very well organized. The page kind of falls apart. There's an awfull lot going on where it comes to color. The colors tend to bounce your eyes from one location in the page to the other. The page definitely lacks color structure. The only reason Google gets away with the color design is because they are extremely carefull not to clutter the page with redundant information.
I'll concentrate on making the page header more visable, to seperate it more clearly from the search results. I'll turn the header into one block of color. This is what it could look like:
Now if I translate this back into the page design, this is what I come up with:
I'd say the page is much more structured now. I'm not saying this is a good design. This is merely a quicky to show what you can do with a bit of color structuring. It would need a lot more effort to make it real good.

Please note that I didn't change the color scheme at all. These are the same old colors. I only applied the colors in a different manner.