What to do with inbound sitewide link?

Recent article claims Google may penalize these

[androidtech]

We provide hosting to a very popular high ranking site. As a thank you they put a line at the bottom of their pages saying "hosted by" and then our web site.

I know there is a large amount of (very understandable) cynicism in our community, based on all the tricks going on in the SEO world, but we absolutely did not buy this link. We happened to like the site a lot (some of us are contributing article writers), so we offered to host it.

I just read an article that claims that Google may be penalizing pages that have lots of inbound links from a single site with the same anchor text, like a sitewide link would.

In our case this appears to be true. Our home page has a page rank of 8, but for our main keyword, we can no longer be found in the SERPS. For non-popular search phrases we show up find and in the #1 position usually.

If there is a Google penalty, what would be our best strategy to get back in the SERPS?

Thanks.