Permalink problem not solved by usual methods

I have a new WordPress 2.8 blog running on my local server (sitting in the same room as me). Using ugly permalinks, all pages are accessible. However, when I change the permalink structure to anything else, I receive Apache2 404 errors.

My .htaccess file looks as follows:

Options +FollowSymLinks
<Directory /var/www/blog>
        AllowOverride Options
</Directory>
# BEGIN WordPress
<IfModule mod_rewrite.c>
        RewriteEngine On
        RewriteBase /blog/
        RewriteCond %{REQUEST_FILENAME} !-f
        RewriteCond %{REQUEST_FILENAME} !-d
        RewriteRule . /blog/index.php [L]
</IfModule>
# END WordPress

Both WebSVN and phpMyAdmin are accessible from http://domain.com/websvn and http://domain.com/phpmyadmin, respectively.

I have tried all suggested fixed on the forums, including:

• Adding custom category and tag permalink structures
• Adding FollowSymLinks and AllowOverride All
• Etc.

Does anybody have any other suggestions?