I have been involved in several recovery stories, though most of them have involved significant efforts in link removals with up to 3 reconsideration requests.
Some of the biggest things that stand out are sitewide links, directory links, and links with commercial anchor text.
You definitely want to try and remove as many "bad links" as possible before doing any type of disavow (as per MC). Generally I recommend a combination of link removals and requesting no-follows, and then submitting a disavow on the "bad links" where you can't get in touch with the webmasters. I'm not sure about changing anchor text, it isn't something we've spent much time on... as we agree with Whitey that if you can change the link, it probably isn't given freely... we suggest that links you can control should be no-followed.