Jez, I wish I could tell you the specific thing I did that worked. Here is what I did since April 24:
* Blocked Google from my development server which was being indexed. Also redirected my non-WWW pages to WWW (widget.com, mail.widget.com, ftp.widget.com were all showing up as valid URLs).
* Asked 4-5 sites to remove blogroll backlinks. These backlinks were appearing in WMT as a huge amount of links to a very small number of pages, mostly my homepage. 3 of them removed them.
* Corrected a lot of issues with duplicate titles and meta descriptions as show in WMT.
* Fixed a situation where a calendar-like page was generating thousands of nonsense pages which Google had been spidering.
* Changed the link structure on a widget I have to be nofollow. This widget shows on other sites.
* Made site navigation better by adding breadcrumb trails.
* Added rich snippets to some pages.
* removed some advertising from each page, mostly a single-unit Adsense ad, a 125x150 banner that I sold myself, and with some thinner pages, a 300x250 ad unit (though this unit still appears on most other pages).
* Updated my vBulletin installation so that nofollow is added to all external links, and cleaned up some forum spam there (I had been actively trying to do this, but the spammers found crevices that I didn't even know existed).
* Nofollowed my "links" page - just about a dozen links on it though, and none were paid or traded for.
* No-indexed a lot of pages that either had no information on them, were search results (and thus not useful to the SERPs) or were infrastructure-type pages (also not useful to the index).
* Added more content to the site, as I have done for the past 16 years. I focused a bit more on rounding out existing topics than on adding new topics, but not enough to make a difference, in my opinion.
Yes, a lot of the changes were Panda-related, but I hadn't been hit with Panda before, at least not noticeably - although a problem I specifically noticed last October, with certain pages not being returned, appears to be resolved too, so perhaps there is some Panda/Penguin interplay involved here - maybe Penguin just makes your site more susceptible to Panda?
Here is why I think I have recovered: Prior to April, in WMT, it showed about 600k search impressions. In April, the impressions got screwy, changing nearly every day, going as high as 1m impressions. Then, April 24, they dropped to about 200k impressions. Throughout the summer they were around 100k impressions. Now, Oct 18, they went up to 450k impressions.
As I mentioned, my site is seasonal, and my traffic is also being hit due to a labor-related issue in my niche which is
causing less interest in the topic, but I have tracked my site's statistics religiously for the past 13 years and from April 24 to Oct 18, there was clearly a penalty in effect - and my experimentation with SERPs showed it as well.