Use reDesign3, if you were not doing so already, and most of the work is done for you. Just add/substitute the major graphics, and tweak the colours - all through CSS. And if you make use of the supplied specific.css to override the default style.css, then you'll not have to change reDesign files per se. So you can update to the latest/future version with little or pain. And it keeps all your changes in one place.
More significantly, it doesn't look like a PHP-Nuke inspired site.
See numerous examples at my site, none of which besides my site itself, look like 2/3-col-Nuke.
It's release worthy - per Eestlane (and in use at several sites) - but he never actually got to formally release it yet. Ii's in CVS, right here on DF.
Big changes in 3, besides the visual ones, is a more organised distribution of CSS styles, so easier to find and edit what you need, and the aforesaid specific.css. And it is more complete in CPG area, etc.