conor - 3:21 am on Jul 27, 2010 (gmt 0)

Major changes to internal navigation can trigger this sort of penalty as easily as suspicious back links and I suspect that in both cases the answer líes in the anchor text.

From what you have written, you have reduced the number of links in your site wide navigation, has the anchor text of these internal links changed significantly? Especially the anchor text of links to the índex page or important catagory pages?

If so I would look to this as this as the source of the problem and
reverse it.