Wow, this is terrible. My problem was a little different. The solution is below.
On WP 2.6.1, the site worked initially with /%year%/%monthnum%/%postname%/. I have WP installed in /wordpress/. I kept the blog viewable at /wordpress as well for development. When I changed the blog address to the root using these directions, pretty permalinks stopped working. I switched it back to the /wordpress directory, without ever touching .htaccess and the pretty permalinks still didn’t work!
After trying many many things, the solution that worked for me:
– dropped the www’s from the wp and blog directory. this forced me to login again. put back the www’s, and logged in again.
– chmod .htaccess to 777
– changed permalinks settings from default, to numeric, and then back to month and name. presto!
– important: chmod .htaccess back to 644
The weird thing: WP never had trouble changing the .htaccess file. I downloaded and checked that it was updated correctly. For some reason, things still wouldn’t work as expected. The steps above are ridiculous, but they’re what I did before things started working again…