I was having the same problem until a couple minutes ago. I just installed WP2.7 on an Ubuntu 8.10 server running Apache2.2.9, PHP5.2.6-2ubuntu4 w/Suhosin-Patch, mod_python3.3.1, Python2.5.2, and mysql5.0. Nothing I tried that was listed in this topic worked, so I did a site-wide search for Rewrite Rules (as I noticed that the Rewrite Rules in the database for 2.6.5 had “robots.txt” and 2.7 had “robots/.txt” and thought this may have something to do with it). Anyway, I found a post from about 6 months ago where a guy had the exact same issue on an Ubuntu server install. Turns out that it was an Apache2 error. The VirtualHost file had “AllowOverride None” for my webroot folder of /var/www/. I added a new directory listing in the VirtualHost file for the blog directory (/var/www/blog/) and added “AllowOverride All”. After doing this the Permlinks work beautifully now!
I had also wiped out 2.7 and dropped down to 2.6.5 previously to try and correct, but it still gave the 404 error and was extremely slow.
