There are some themes with SEO aspects built into them. Thesis & Headway for extreme examples usually require no additional plug-ins that are SEO orientated.
I could see how a change in theme could change a ranking, both positively or negatively.
Also keep in mind any change can cause the dance.

ANY change has the potential to affect your ranking.

If you are established with many incoming links on an aged domain changing from one well constructed template to another with the same data set should have little effect.

I have changed entire platforms from html, to joomla, to wordpress without affecting my ranking.

Make sure you plan the change and look at the structure of your site from a bots perspective. Bots can only follow the links you give them.

Yes it can, but I think not extreme like that.

Themes can affect SEO depending on how it was built, but I doubt it will bring your site up 4 pages on Google overnight. You must have done something before (link building, etc) that took a while to take effect. Most likely a coincidence that you changed your theme the day before.

I know from experience that changing themes can drastically affect SEO. I changed themes a while back and the Google spiders weren't sure how to read and rank the new theme I was using (the ranking and meta description changed on and off for a few days), so instead of ranking me highly, the spiders slightly penalized me because the theme wasn't easy for the search engine to read.

I was late to give you my opinion. Yes, It does matter. Usually related with Keywording H1 and H2

yes but it not so much.Some wordpress theme is terrible for SEO.Check it vailid with xhtml

It all comes down to a number of things including:

#1 How well written the new WordPress theme is compared to the old one. It could have been easier to crawl.

#2 Essentially as above, badly written Javascript could cause search bots headaches when they crawl your website as it could be hiding some of your content.

#3 If you've left the footer links intact, they could be deemed spammy especially if the author has chosen to add loads of paid inclusion links to shabby websites. Obviously if the link is to the authors website only, then this shouldn't be a problem.

#4 Maybe it's just Google having a bad day/week/month and your website will be back to where it was previously before long.

#5 All or none of the above and/or something completely different...

@katy2005

It's all well and good being sucked into the whole "Premium themes are better than free themes" debate. And to be honest, I guess most of the people who claim that Thesis is helping them rank any better in Google is probably blowing smoke up their own ass hoping to try and convince people to click on their Thesis affiliate links and buy the theme themselves.

There are more than a few good themes and theme frameworks out there which don't cost a penny and do just as good a job as Thesis and another Premium Theme. Writing good original content on your blog is all that's needed to get the search engines interested in visiting your website. Not spending $200 or whatever they cost, on a "Premium SEO Theme"...

One tip is to utilize redirects for any modified or non-existent URLs which occur after the update. You simple do not want the spiders to find broken links, or 404 pages.

crap, need to change one of my themes, one I have is not working out...

Thesis is a good theme, no doubt, we use it on several sites, but the onsite SEO on a site is only ever going to be as good as the structure you build into the site, and the content.

Thesis is good because you know its definitely not going to mess up your SEO by installing it, and because it has pretty much all you need SEO-wise.

but ultimately if you're selecting between several good themes, the theme is really just "the way it looks"

Yes i can confirm that changing your theme will result in a negative change in rankings. I changed from free wp themes, to new headway theme. And all my sites i changed, dropped like flies on google.

Definitely, my main site has dropped after changing the theme - so I'm spending time working on new backlinks and generating traffic to remind Google that it likes my site. As long as the theme you move to is optimised for SEO you should see it recover with a little TLC.