Changing the colour can range from REALLY easy to moderately difficult depending on the theme. If it's all done in CSS and uses the Xenforo color palette, it's literally a couple of clicks in your admin control panel to change the colour. Some themes even have a built in colour options. If you need to start editing images/gradients then it becomes a bit more difficult but it shouldn't be out of the question.
Again, I'd suggest you talk to
@pixelExit.com (
@Russ and
@Steve F) who are excellent (and cheap!) when it comes to all things theme related. Even if you just want a bit of expert advice I'm sure they'd help.