A friend has a large site that got hit with a similar penalty in a similar situation over a year ago. Like in your case they were agressivley adding links (un paid but looked pretty paid) and had just made some major sitewide navigation changes when the penalty hit.
They removed the questionable IBLs but for buisness reasons ( Google was responsable for 70% of the traffic but only 20% of the revenue and the site upgrade included much needed usabilty improvements which increased conversion) they rolled back most of the changes and cleaned up everything that looked even a little manipulative but kept the new navigation in place.
A year on they are still penalised ...
Rolling back and carefully adding one change at a time, slowly and systematically and monitoring the results really is the way to go if you want to get this lifted.