fathom - 7:24 am on May 4, 2013 (gmt 0)
Just changing domain names without attempting to fix anything that potentially caused the problem would be like changing socks without taking antibiotics and wondering why the new socks didn't cure the big infected foot wound.
A new domain of subdomain would only get you away from the flag on your domain, you would still need to make some changes and fix whatever might have caused the problem.
Any keyword stuffing, title stuffing, link madness, etc. would need to be addressed.
Basically, a nice plain vanilla site made for humans and not geared for any type of SEO whatsoever would be where I would start and see what happens, then slowly make SEO changes and not get aggressive about those changes.
I'm finding these days that less is more when it comes to SEO because too much invalidates the whole thing and you're sitting there with a ton of work nobody can find.
No one claimed is was easy to recover you really have to put some serious brain cells to work on all the issues involved. Just because link & link anchors drive to the forefront of the common issues not every DIY is capable of analyzing everything involved.
"Lose" implied the loss of link juice asssociated with the links that are obviously still there.
Actually, I did not lose any backlinks after Penguin. Since then, I've lost a few and gained a few, as one does when one is letting the links happen naturally.