I just upgraded to 2.0 and now the permalinks don't work unless I use the "default" setting. If I use "Date and name based," my preferred option, the permalinks all display correctly on the blog, but if I follow them, I end up with the main index view of the front page. It does, however, display the intended permalink in the URL window.
I tried renaming my old .htaccess file in case there was something in there that might be confusing WP 2.0, and then rebuilding the permalink structure, but that didn't seem to help.