Also, to another reply a bit further down, I actually started fresh with a new domain about 6 months after the initial penalty, and used 301 redirects from the old (penalized) site to the new.
I did this to reduce confusion from my existing users, as their was no reason why they should have to retype or bookmark a new domain name. Sure I was going through a very rough patch, but my users should not have to as well!
I had a simple bit of logic that said if you were coming from the old domain, to pop up a message say hi, we had a name change. Not ideal, but that's the best I could come up with.
Little did I know that the 301 actually transferred the penalty to the new site. Shortly after launching I was hit with a second penalty, and the thought of having to change domain names again was just...it's just wrong. The inconvenience and confusion this creates for users is still being felt to this day. I routinely get emails from users of the first domain asking if I'm the same company.
So yeah, I've been trying here, but my lucks been pretty bad : )
... and then google comes out with the disavow tool
!