brinked - 8:02 pm on Sep 14, 2012 (gmt 0)

sidebar footer links can be a big no no. Are these sitewide links? If so, that can be part or the main reason behind the de-indexing.

What about the actual page itself? How many external links? Any hidden text/links going on here?

I would not say you have an over optimization penalty. An over optimization penalty is a name that generalizes ranking losses due to excessive seo tactics such as keyword stuffing (in the title tags, body content or even excessive use of the same/similar anchors in backlinks).

While you may very well have an over optimization penalty, that in itself does not help you because its not very specific.

The problem most of the time is usually the webmaster thinks they did nothing wrong. The way you talk about sidebar/footer links you actually believe these are positive factors for your website when usually they are not.