tedster - 6:27 pm on Dec 16, 2012 (gmt 0)
I fixed the problem by redirecting all the error URLs to correct URLs.
That's a key step when you change Permalinks for old pages. Then it's good to change any content area links to the new Permalink too, rather than send them through 301 handling. Depending on how you changed your permalinks, plus how many content area links you've got, that can be time consuming. But it is a good thikng to do and helps your site circulate PageRank internally in a more efficient way.