New post from the Search Engine Roundtable: Someone “…received a response from Google to a reconsideration request that the only way his site will be reincluded in Google is if he removes all or most of the links in those WordPress themes.” The problem is that those links are in the form of sponsored links on footer (a practice I saw a lot in the past, not so much in the present).
I don’t think it will be easy, or even possible, to do what Google requested. If a theme contains an upgrade notification feature it might be possible to do, but even then the users might choose not to upgrade.
Secondly, if this is true, I wonder whether Google differentiates between credit links (“Designed by…”) and sponsored links. I would say they should, but then again I’m not a SEO guy.