I updated to 2.6 on a dev site and now permalinks and category links are broken.
My permalinks have been in the format of: http://host/wp/index.php/2008/05/post-title/
Categories are like so: http://host/wp/index.php/category/category-name/
Now both return the 404 page.
The main page of the site and the control panel and things all seem to work fine.
The wp/.htaccess is the same on both the dev site (2.6 and broken) and the live site (2.5 and working). I've read other posts about setting the permissions on .htaccess and letting WP write a new one. I set it to 777, but WP doesn't modify the file. (And it didn't in 2.5 either.)
Honestly I'd rather drop the index.php from the links anyway, but I was never able to get that to work.