I had the same issue. Many sub directories were renamed and www.moz.com / www.xml-sitemaps.com for almost a week now have been throwing massive amounts of 404s. The failing links are combination of the previous and new site structure.
I also would love to know if there is an optimal way to roll out changes to minimize the problems of searching for legacy directories. And does it negatively effect a sites reputation with the index?
