superbitz - 5:55 pm on Apr 9, 2013 (gmt 0) [edited by: Robert_Charlton at 12:12 am (utc) on Apr 23, 2013]
I second jimbeetle: fire the SEO company. More than that, don't be afraid to throw them under the bus when you craft and submit your reconsideration request (and you will need to do that).
Remember as well that Google wants to see a GOOD FAITH effort on your part to prune unnatural links before you resort to the Google Disavow Link tool and before you submit a reconsideration request.
To see what you are up against, <snip, to the effect of: check your backlinks at one of the free sites online.> It's not super accurate but it will give you an idea right away of how much work you really may have to do here.
Good luck and keep us updated!
[edit reason] removed specifics, per forum Charter [/edit]
[edited by: Robert_Charlton at 12:12 am (utc) on Apr 23, 2013]