The challenge site owners face in cases like this is sorting out two issues.
One - there is a Penguin demotion, and that's algorithmic.
Two - there was an unnatural links warning, and that often comes just before a manual penalty.
The exact dates of traffic loss should help sort this out. update references [webmasterworld.com]
No matter which cause is in play - or even if it's a combination - you've still got to fix that heavy-handed backlink profile. Since there's a warning message, you can and should send G a Reconsideration Request when the clean-up is well under way.