Color combination is very important for adsense earnings.. Also the ad positions should excellent for high traffic conversions!
Yes, it can change SEO. Changing the template is effectively changing the code of the whole page, so it is possible that all the <H> tags will be different, there will be a different order to page elements etc...
While changing the templates, take care to place the ads at vantage points and blend them with contents (of course, without overdoing it!) and see that the chosen template is reader friendly and gives a pleasant experience for your visitors.