If you assume you know what the right colors for everone are, then you are naive.
Different people need different color themes depending on:
- Their vision
- The surrounding lighting (see these two answers: TVs, Sunlight)
- The specific content they are looking at (e.g. uniform colored text vs graphics or multi colored text)
- and even their mood.
Look at these two themes for example:
Some people will find the first one more comfortable and some will find the second more comfortable.
The first might be more comfortable for standard people who prefer things that don't stand out, while the second might me more comfortable for people that prefer to focus on the images, that stare at computer screens for hours in a row or that need higher contrast due to vision problems.
The key to getting this right without loosing your branding is the keep the brand's colors, but play with the contrast - e.g. keep the blue as in the above example or change the brightness of the blue. Or if your brand is based on high contrast colors e.g. black and white or yellow and brown, swap the two colors.
Also, make this change cross sites (for all your companies sites) to keep the experience the same.
You should of course create a limited amount of verified themes (verify contrast of all parts, brand colors, look of simplicity and etc.).
As the others stated, if your clients have brand their parts of the site, let them choose the colors, however, let them create a few simple themes each by determining the colors of types of content (e.g. title text and BG, regular text and BG, menu text and BG) - do not give them too many parameters to change, since they may loose control. Also, verify the colors programatically (contrast, max number of different colors used (except black, grey and white)) or better yet, give them a medium range of ready made themes to choose from.
Edit: I think a minimal set of themes (which would not interfere with most brandings) should be light grey on black, dark grey on white and perhaps also white on dark grey and black on light grey.
To make sure the theme is as browser neutral as possible, make sure you override all the colors and don't leave any colors on their default (browser or OS) values.
On a side note: the TV tonight section's text to background contrast doesn't look high enough (in either image).