incrediBILL - 3:57 am on May 4, 2013 (gmt 0)
Well,im in the same boat you guys are in and I changed my domain name last year and still can not recover
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.