Believe it or not I'm with you on the colours. I was given a template constructed with tables to start with and commited some grevious offences with colours in the first incarnation. The boss liked it though, so it while I toned it down a bit (I know that's hard to believe but it's true!) the overall effect had to remain the same when I reconstructed the site.
I am interested in the 'dated' comment. Is there anything in particular or is it the feel of the site as a whole?
What would you do to 'update' it?