Did you make them all at once, or did you make one, then another, then another?
Basically all at once, as much as changes like we made can be. Link removal took about a month with the reconsideration request and list of links sent once that was completed. Heavily linked page/directory removal happened at the same time. All changes took place within the 2 months following penguin.
Now it could be said that what we are seeing is not "non-recovery" but in fact simply ranking appropriate to the fact that we have not done any seo since removing the bad links. For example: we could have been ranking #1 for keyword due to spam links, once those links were demoted/removed we no longer had any basis for ranking for that keyword.