WP 3.2 fresh linux install permalinks not working

Hi, I have an issue that I have seen posted various times over the last few days already but I haven’t found a solution yet.

WP 3.2 fresh install
PHP Version 5.2.6
Linux 2.6.26-2-xen-amd64
CGI/FastCGI
This server is protected with the Suhosin Patch 0.9.6.2
Apache2 mod_fcgid/2.3.6 mod_perl/2.0.4 Perl/v5.10.0

PROBLEM: when I set the permalinks to anything but standard, I get a “forbidden” page (as soon as I delete the content of the .htaccess, everything is obviously fine again).

I set permalinks to:

Month and name http://XXXXX.com/2011/07/sample-post/

I get:

Forbidden
You don’t have permission to access /wp-admin/options-permalink.php on this server.

My .htaccess contains:

# BEGIN WordPress
<IfModule mod_rewrite.c>
RewriteEngine On
RewriteBase /
RewriteRule ^index\.php$ - [L]
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule . /index.php [L]
</IfModule>

# END WordPress

Any idea what it could be? Mod_Rewrite usually works on all my other sites….