As Yukon previously mentioned it might be worth it to change the url of a page when only the specific page has been hit/penalized. We tried and it worked, got the page back for that keyword at #2 above Google Places in less then a week.
For the rootdomain there is not really a solution but for the innerpages you can rename the url and redirect the old url to the new one in the .htaccess file that you find on your hosting in the rootmap of that particular domain. We've tested this on a large site that got penalized hard and the rankings are all back, not as high as before but certainly not beyond page 5 anymore.
The thing is, you have probably been penalized for bad links or poor anchor diversity so by redirecting 301'ing the old url you get rid of that. First I thought all this anchor diversity was a bit over hyped up but as the redirects proof to be working it seems to be more true then ever as you don't have any links/anchors pointing directly at your url anymore but only at the old one.
This way you still remain your old links that always worked.
Another thing that you might've been penalized for is losing a lot of links after the blog network deindexing, when you lose a lot of links you not only lose the juice but also the popularity of that page (in Google's eyes) and that leads to a penalty. When you have a brand new page you don't have that problem and thanks to the redirecting you still get the juice from your remaining links.
Think about it and try it yourself. So far we had great success with this renaming of the urls and 301'ing the old urls. No guarantees but hey, you got nothing to lose anyway!