Erro 404 quando altero os permalinks

Olá,

Estou tentanto alterar os permalinks do meu site do default para /%category%/%postname%/. Porém, toda vez que altero para esse ou qualquer outro formato que não seja o padrão, os links da página principal redirecionam para a página 404.

* Usando apache 2.2;
* O mod_rewrite está habilitado;
* Já alterei o .htaccess para:
<IfModule mod_rewrite.c>
RewriteEngine On
RewriteBase /
RewriteRule ^index\.php$ – [L]
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule . /index.php [L]
</IfModule>

Alguém poderia, por favor, me ajudar com isso?

Agradeço desde já
Fábio Vasques