Over Optimization with Footer Links

So I have a potential client that has been slapped by the penguin. His site is ranked for a real good keyword phrase, but he has like 64k backlinks from the same site. Most of them are footer links and it is a relevant niche (about 60k). I am about 90% sure that this is why his homepage is getting penalized because it is all the same anchor text.

I was thinking about adding the highest quality links I can, but I'm afraid it might be a difficult task. This is his biggest money making site so I am not sure if a 301 redirect will be acceptable. Should I get the footer links removed or just try to build quality on top from now on?

If it is the footer links, get quality links isn't going to do much.

If I was you, remove the footer links, and when Google crawls it and refreshes the index, see where you end up.