It has now been over six weeks since Penguin 2.0 was released and I have yet to see any credible cases of recovery. Recently, in a Webmaster Central Hangout, John Mueller gave some vital information when it comes to recovering a site that was affected by the Penguin algorithm. We know that the Penguin algorithm is primarily about the quality of your backlinks. Most SEOs postulated that removing or disavowing spammy links should make a huge difference in a Penguin hit site's rankings. However, many people did this and I have not seen anyone proclaiming recovery once Penguin updated on May 22, 2013.
Here is a Webmaster Central Hangout where John Mueller gives more information on this. Start watching at 28:33.
The question asked was whether or not it truly is possible to recover from Penguin. Here is a transcript of John's answer:
If your website was ranking badly because of those problematic links, then, by cleaning those up that's definitely something that our algorithms will take into account, and that's definitely something that the Penguin algorithm as we re-run it and reprocess the new data will automatically take into account. It's not that being affected by some algorithm is a one way street and you can never get out again. If we find that things are cleaned up then those algorithms will take that into account and bubble that back up in the rankings as well. It's definitely something that, if cleaned up properly, things can work really well again.
One thing to keep in mind, specifically with regards to link issues, is that, if your website was ranking well because of those problematic links in the past, then by removing those problematic links, essentially, the basis for your site's ranking will be different afterwards. It's never going to be the case that by cleaning up all the issues around your website, your website will automatically, on its own jump back up in rankings again. Essentially, if those links are gone and we can't use them positively for your website anymore, then that's something that the ranking algorithms might have to compensate for again. Just removing the problematic links won't automatically result in your website jumping back up again to where it was, maybe artificially, because of those problematic links.
So, if you're cleaning things up for your website, I'd definitely recommend cleaning up the problems but I'd also work on making sure that you're actually providing a lot of high quality, unique content on your website as well that users will want to recommend on their own. That's essentially something that has to go hand in hand. It's not that you can just clean up the problems and things will jump back up. You really have to work on making sure that your website is the absolute best that it can be.
Related: Penguin "recovery" stories.
TL;DR: You CAN recover from Penguin. To do so, you need to clean up your backlink profile AND also be able to attract links naturally which is no easy task.