reblaus and Indyank
Regarding when you'll see ranking improvements due to your changes/tweaks (I'm waiting just as you guys are), I wanted to suggest that you look in your Google Webmaster Tools console and check the crawl data. There are some graphs that show the spidering volume and crawl frequency. I see daily spidering, but I get a different spider with a deep crawl about every 45 days. In the past, when I have seen penalties, they were both initiated and removed as a result of this deeper crawl/spider. And just last week, I got a deep crawl (first one in a month), on March 10, then I was penalized by March 11. I have continued to see minor spidering since, but obviously no positive changes in rankings.
So my guess is, I will have to wait until that other spider comes around to re-rank me. So glance at your crawl charts (or your raw data) and look for spikes (in the raw data, I believe it's Googlebot/2.0). Then, you can estimate your deep-crawl frequency and how long it might take to see it come back around.
I'm sure spidering frequency is related to numerous factors (authority/trust, content updates, etc), so some sites get crawled more regularly by the bot(s) that really matter. I am not so fortunate. I sometimes have to wait 45 to 60 days to see that spike. Just don't beat your head against a wall everyday by hitting refresh on the results, because they aren't likely to change (unless it's your time to get re-ranked).