Permalinks issues

Hi,

I’m trying to change the permalinks in my site from defatul to /%category%/%postname%/. However, every time that I change to this or to anything different than the default, all links in my site are redirectioned to the page 404.

* Using apache 2.2;
* mod_rewrite is enabled;
* My .htaccess file is already like the instructions:
<IfModule mod_rewrite.c>
RewriteEngine On
RewriteBase /
RewriteRule ^index\.php$ – [L]
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule . /index.php [L]
</IfModule>

Could anyone, please, help me with that?

Thanks in advance,
Fábio Vasques