When we upgraded from 2.5.1 to 2.6 links to the individual posts started throwing 404 errors. After a little digging around we found this fix on wordpress.org:
If you need/want the index.php to be there, then on the Settings->Permalinks screen, add some values in for the category and tag bases. The words “category” and “tag” will do just fine. As long as they are not blank, this should work around the bug.
I hope this helps some other people out there who were gnashing their teeth like I was 5 minutes ago.