Site não acessa index.php automaticamente

Quando mudo o permalink para /%category%/%postname% e acesso o site, por exemplo ‘www.exemplo.com.br’, ele não abre, da erro de não encontrado, porém quando acesso por ‘www.exemplo.com.br/index.php’, ele carrega normalmente porém mesmo assim, quando clico em alguma categoria ele me retorna o mesmo erro:

Not Found
The requested document was not found on this server.

Então mudei o permalink para /index.php/%category%/%postname% e quando clico em alguma categoria ele carrega normalmente, http://www.exemplo.com.br/index.php/category/categoria
porém ele continua não indo direto para o index.php caso eu entre só por ‘www.exemplo.com.br’ e da o erro de Not Found

O que poderia estar acontecendo? Eu queria que os links fossem http://www.exemplo.com.br/categoria/nome-do-post.
Engraçado que quando estou rodando o server no meu proprio computador, ele funciona.

meu htaccess :

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

Muito obrigado.