Permalinks not working

So I have made a FRESH install of WordPress to start an ADULT BLOG on http://www.pukkabdsm.com/
the problem is that when I use the the Permalinks with the following settings:
Custom Structure: /%category%/%postname%/
Category base: /%category%
Category pages: /%category%

.htaccess file:
<IfModule mod_rewrite.c>
RewriteEngine On
RewriteBase /
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule . /index.php [L]
</IfModule>

the Permalinks work fine for the MAIN CATEGORIES (ex: http://www.pukkabdsm.com/general-bdsm-info/
http://www.pukkabdsm.com/bdsm-porn/ )
but when trying to reach the SLAVE CATEGORIES I get redirected to the INDEX OF THE SITE.
when I try to reach the post pages I get redirected to the INDEX OF THE SITE (I was getting 404 errors before).

when I do a search : http://www.pukkabdsm.com/?s=BDSM
I get the proper results page, but then I click the links, the DON’T open as they should (I get the same errors I already mentioned)

I have tried lots of other configurations on the settings for the permalinks, but none solved all the issues, with this setting I made the NAVIGATION WORK…

thanks in advanced for the support!