triggerfinger - 8:56 pm on Oct 10, 2012 (gmt 0)

I'm pretty sure they are referring to links on external sites' footers, pointing back to your own (the clients website example mentioned above is probably a good example). Your own internal footer links wouldn't be considered a "scheme", I don't think.
Focus on the user's needs, and I think you'll be ok. Footers are useful for users' navigation, and like other navigational links, are probably devalued, but don't call it a penalty.