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:

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.