Once fixed you will have TWO sets of urls and the "fixed" version will start to gain history. If you 301 the old to the new and/or robots.txt block the old, and possibly even perform a removal request if you take the robots.txt route, you can be assured that the new will outrank the old.
That being said the old url's will need a good long time to fall out of your link graph, even if they don't rank in serps. Google forgets nothing.
I would 301 redirect the old URLs. You want to retain the traffic for at least as long as other sites are linking to the wrong URL and certainly while the old URL is listed in the SERPs. Second best is to return 404, or meta noindex. Worst way is using a robots.txt disallow.
It will take at least a few weeks, often a few months for the SERPs to be cleaned up. It may take 6 months for the URLs to drop out of the WMT reports. That is NOT a problem.
I think it depends on overall frequency of crawling rather than calendar time. I have one directory that I created in January, with 301s in place at the outset. Google still crawls the old URLs about twice a month. I know because I've been waiting for them to stop so I can clean out my htaccess. The last time I did this, msnbot or someone like them came knocking at the door within days-- literally-- after I'd decided everyone had accepted the changed URL so it was safe to drop the redirect. Grrr. But now they can bloody well take their 404 and lump it.