That sounds like a carbon-copy of what happened to us in late march of this year. Here's what I've been doing to get that (always nice) free Google traffic back.
1. Started a tightly focused, on-topic only linking campaign. This hasnt been easy for us, as we're kind of a niche, but in the last 6 months we've gone from a handful of inbounds to over 300 (and our pages linking to these sites also rank well, which helps attract more traffic partners).
2. Reduced keyword density slightly. This was done more to add associated words/phrases to expand the keywords that our pages come up for.
3. Used Ask.com to search for the kinds of phrases/questions that our potential customers were asking about the product we carry, then wrote articles specifically answering those questions. This has single-handedly broguth in an additional 500 or so visitors per day. If you don't have time to write, just hit up elance for a ghost writer.
4. Optimized our Froogle feed: This wqas simply a matter of taking a look at our competitors titles/descritpions that were coming up #1 in froogle for similar products and using that as a model for ours. The result: An additional 3-5 froogle generated sales per day (not to mention we now appear ABOVE the #1 result for the majority of our targeted phrases).
So...having said all that, you're probably wondering if we've regained our top 10 postions that were lost in march.
Not quite. However, we've gone from page 30+ for most of our categories to no further back than page 9 (again, this is only google, everywhere else we're rocking!).
The biggest thing I learned is that our site will never be "finished", you can never have too many incoming links, and if you take the time to write article that answer your potential customer's questions, you can really clen up on the traffic.
Now, here's the kicker:
Prior to our "fall from grace" into the sandbox (or whatever caused us to drop into search oblivion) we were getting roughly 3000 free uniques per day from google. Now, since doing all of the above, even though we're far short of our previous positions, daily uniques exceed 4000!