Your site should have been hit on Jan 19, 2012 for having too many ads above the fold. If that's the case, let us know when you did fix your page layout and how long after your got your traffic back.
I think I read on an article that the algorithm is run manually periodically. So if you make any changes to meet Google best practices, the results may not be apparent immediately. When the next "run" is made, you may then be unbanned.
@infonote, this is what the official Google webmaster central blog said: "If you decide to update your page layout, the page layout algorithm will automatically reflect the changes as we re-crawl and process enough pages from your site to assess the changes. How long that takes will depend on several factors, including the number of pages on your site and how efficiently Googlebot can crawl the content. On a typical website, it can take several weeks for Googlebot to crawl and process enough pages to reflect layout changes on the site." But, we want to know if anyone has actually recovered the traffic as we have not found anyone just yet.
i think im having this same problem i was offline for a year and didnt know about this new change and added to many ads at the top, and now i had to remove them i hope it helps soon.