This would of course depend on how much of your site needs to be changed.
If you want to give it a try and do this your self, it is in fact rather easy
You pick one color you are not going to use
activate the custom.css file in the template manager settings.
copy the css style of the color you pick into the custom.css file
search for the color you are changing out and replace with the new one (this you can do on the Cpanel if you are hosted where you have full access of your files)
then you can open up the template's images folder, and download for example the menu images, site background etc..and open up in photoshop, color them with the new color and upload and overwrite.
let us know here if you don't trust your self to do this on your own, but it is very hard to estimate such work without at least a link to the website