A Google Webmaster Help thread has a webmaster who changed pretty much all the URLs on his web site. He did set up proper redirects, but is patiently waiting for Google to reindex the site and capture the new URLs. In response to a question, Google's JohnMu replied with the following statement:
As freebeer mentioned, my guess is that this is from a time where your site did not have the proper redirects in place. You can guess to see if this might be the case by checking the crawl dates in Webmaster Tools. If you've had the redirects there for a while now, then I would check to make sure that the errors are mostly from before that time. If that's the case, then things should settle down over time.Keep in mind that changing all URLs like this will result in changes in the crawling, indexing and ranking of your site -- since we're essentially seeing new URLs for all existing old URLs. This is not something that can change over night, so you'll have to be a bit patient and keep an eye on the logs to make sure that everything is covered, as things settle down.
Sometimes changing URLs is a must due to programmer requirements (although that is a lame excuse), due to previous duplicate content issues or due to management requirements. But changing all the URLs on a web site will have an impact, at least in the short term.
JohnMu cleverly links to a W3.org article named Cool URIs don't change. Be cool, stick with your cool URLs.
Forum discussion at Google Webmaster Help.
