Changing permalink stops me from creating webpages

Question

I've just created a new WordPress site. When changing the permalink structure I cannot create or edit pages. I do have mod_rewrite enabled but alas still get errors. How can I fix this? I've had this error before with mod_rewrite enabled but can't remember for the life of me how I fixed this, any ideas?

Here is my .htaccess file:

# 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