I had a similar problem after the 2.7 upgrade...
It started with one post not showing properly when viewed singly and then went to two and then today it went bonkers and nothing showed as individual posts! They showed on the default front page list though.
So after fishing around the web I eventually ended up here and tried a complete roll-back and part-re-install.
I took out all the plugins that had anything to do with permalinks and caching:
Broken Link Checker
Deans Permalink Migration
Enforce www. Preference
Google XML Sitemaps
I've been mixing and matching with these things over the various incarnations of WordPress, mind you, so they weren't all on when I finally pulled the plug, so to speak.
I then flipped Permalinks back to defaults and the menu structure and posts' links worked correctly.
On going back to pretty permalinks I still had no joy...
I then re-uploaded good copies of all files in the root and wp-admin folders (I didn't do wp-includes), overwriting everything.
But still no joy... (BTW, in all these tests, I used Firefox and Opera, refreshing each time).
So I followed @Madsk's words above and whipped out the old htaccess by renaming and made a new htaccess and just added the single line suggested, set as 777.
NOW the pretty permalinks started to work and WordPress wrote it's stuff to htaccess.
Now it's really curious... I copied the "new" WP generated code to the old htaccess file, overwriting the WP code at the bottom, where it was anyway... IT WAS EXACTLY THE SAME!! Then I swapped the files over (by renaming using my Hosting client) keeping exactly the same previous permissions of 644.
And STILL everythings works! Why? I don't know, but I'm happy!
My next task is to re-enable super cache and google sitmaps and then gingerly try some other plugins. Redirecting I can probably live without now as the number of posts on the current permalink structure massively outnumbers those on the old default system I previously used.