I don't think a refresh is going to help.
As far as I can see, Penguin was a recalculation of a websites linking pattern with relevance as the base for PageRank calculations.
With the removal of the non-relative link's influence on SERPs, being part of the equation there will not be a recovery.
The other part is a set of penalties based on the anchor text found on the non-relative links.
These are tough penalties.
It seems they will even follow across to a new domain, if the old one is linked, or perhaps if the owner is the same in the whois check.