We’ve spent HOURS on the permalink issue as well. Went from (I think) 2.1 to 2.6 and lost categories as well as permalinks. As long as we used the default link structure, it was OK. (rebuilt the categories to fix)
We also had a new RSS feed address (old one involved index.php, new one didn’t). RSS feed issue was fixed when we upgraded to 2.6.1 yesterday.
We’ve tried EVERY recommended solution for the permalinks. Finally found one that worked:
index.php/%year%/%monthnum%/%day%/%postname%/
We’re running Apache.
If you have a blog at index.php on Apache, definitely try the index.php custom path.
Thanks all for the help…
(edited to clarify upgrade to 2.6.1)