raymondcc - 7:11 am on Jan 13, 2013 (gmt 0)
I used to have automated translation plugin for Wordpress and vBulletin which was later removed. Obviously that quickly caused over a hundred thousand 404 errors in GWT which shortly after the traffic starting dropping like crazy.
I can't really remember exactly how long I waited but it was more than 6 months for the traffic to stop dropping. Recovery wasn't a lot as well because my site was hit by Panda.
When Google said 404 do not affect rankings, probably they meant a few 404s, not thousands of them in a short duration.
What I did to fix the 404s from the GWT is to block Googlebot from visiting the invalid pages using robots.txt. If the invalid pages are found in SERPS, I used the "Remove URLs" from GWT to remove them. The number of 404s in GWT starts dropping and now it's around 5000+ which is so much better than 100,000+.