A concur that Google devalues footer links almost completely. Links in the left or right gutter below the fold do slightly better. Breadcrumb and tab navigation above the fold appear to me to be effective.
I also think that Google does not like blocks of more than 10 links. And Google does not like repetitive anchor text within blocks of links.
In other words, there are some links you put on the page only to pass pagarank around internally. Google knows this and frowns on it. Try to find navigation that features what you want to pass your pagerank to that users actually use.