I’ve been having the same problem.
I’m not exactly sure what fixed it for me but my settings are as follows:
.htaccess:
# BEGIN WordPress
<IfModule mod_rewrite.c>
Options +FollowSymLinks
RewriteEngine On
RewriteBase /wordpress-e/
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule . /wordpress-e/index.php [L]
</IfModule>
# END WordPress
httpd.conf:
I changed AllowOverride None to AllowOverride All *wherever* I found that line and the pretty permalinks are now working.
Now to try and find out what I actually did that made a difference.
Hope this helps someone.
btw: httpd-2.2.3-31.el5.centos; WordPress 2.8.5
