@fathom, yes, I mainly made improvements to my site that were not focused on backlinks - but I did so because I had no other options. I didn't have a spammy backlink profile. I had to try something.
I don't know why my site recovered. I doubt even Google knows, since the penalty was algorithmic. It's very possible that my profile was a false positive and Google corrected their algorithm - in theory I could have had a backlinks problem due to my site being so heavily referenced by Wikipedia, and then being duplicated so many times on so many Wikipedia clones. It's possible that improvements to my site navigation appeased Google. It's possible that the seasonal change in my traffic caused my site to overcome a penalty. It's possible that the fact that I removed an adsense unit from each page tipped the scales. Or maybe it's a little bit from each of those things. I don't know.
Google's advice on the topic is, quite frankly, patronizing. They basically say "if your site isn't the best it can possibly be, then that is your problem". EVERY site can be better. Even Google.