BillyS - 2:42 am on May 10, 2012 (gmt 0)
It's interesting that you think keyword stuffing is your problem. Most of the comments I read had more to do with gaming of links.
Matt Cutts used to talk about writing for search engines. Maybe someone here knows the reference. It was either on his blog or in a video. He actually explains how writing a certain way can actually help search engines. I follow that practice myself.
If you search for "google keyword stuffing" you'll find a WMT article that talks about this practice and penalties. It's always been on Google's radar and you can fix the problem then submit a reinclusion request.
I think it's been pointed out that Penguin is a ranking factor, not a penalty. Just like Panda, you cannot submit a reinclusion request. You keep your fingers crossed that the algo re-ranks you.
We weren't hit by Penguin, only Panda :)
Unless you really feel you were keyword stuffing, I would be careful about making too many changes too quickly. As much as it pains me, I'm taking a very methodical approach to seeing what might have tripped us up.
Best of luck to you.