I just inherited a blog from my brother. Yesterday, I upgraded it from 2.7.1 to 2.8.4. When I tried to change the permalinks from /?p=123 to /%category%/%postname%/, it didn't work. (404 error.) (I had to manually update .htaccess due to write permissions on this particular host.)(Linux, Apache.)
That is, it didn't work until I went in and edited each individual post...about a 4 hour job, thankfully there were only 46 posts when I took over admin duties. I also added tags while I was at it. (My brother had used no tags at all!) Articles can be found using tags links from the tag cloud with either type of permalink enabled.
Now, I can switch back-and-forth between default and custom permalinks and the links to the articles work fine. But when using custom permalinks, the category links are broken! WP can find no articles in any category until I switch back to the default "ugly" permalink style.
I tried using the migration feature in the advanced permalinks plugin (http://urbangiraffe.com/plugins/advanced-permalinks/) but to no avail.
I have tried activating/deactivating all the plugins. All I get when clicking on a category link in the sidebar when anything but the default permalink is being used is "Nothing found for category {whatever-category-i-clicked-on} in the title bar and a corresponding error message on the page.
I tried using different themes. The only thing that changed was the error message text on the category page.
I tried creating a new category and posting to it while permalinks was set to /%category%/%postname%/, and it worked!
So, I thought, why not just rename each category to something temporary, create a new category with the desired name and slug, then move all posts from the old renamed category to the new one? (Another 3 or 4 hour task probably, but if it works...) Well, moving an existing post to the test category I created did not work. Clicking on the link for the new category brought up only the article originally posted to that category, not any existing posts that were moved.
Also, if I change the slug for the new test category, it breaks it. Changing the slug back to what was originally used when creating it repairs it. Switching back to default permalinks has no effect except for what is displayed in the title bar. (.../?cat=226 vs. .../category/test.)
Any ideas?