It totally depends on just how different they want it.
I'm not a programmer but I know better than the basics of html and css and I always customize the WP templates I use.
Generally changing colors can be fairly easy but it may involve more than just changing the html color codes. Most themes/templates rely on jpg or gif files as background, etc. so it would require pulling those files into Photoshop and making the changes there. If you like, I can take a look at what they have and what they would like and let you know what kind of help they may need.

__________________
~Christina-Business Darlings-Magazine for Virtual Business Owners