I am really surprised to hear this, since footer are harmless and moreover footer links from other websites, especially your client's is highly worthy.
There might be some other reasons for your ranking downfall. You may have lost some of your precious backlinks, so try finding out which links you had lost in the last couple of months and make sure you get it back. Else, you might have stopped building links or getting natural links to your website. I would recommend to get some backlinks for the desired keywords either by article submission or through blog comments.
Moreover, there is yet another advantage of having links from your client's website's footer and that's brand promotion. You are advantageous of getting some good references through your client's website, so think in that perspective and maintain the links.