Permalinks not what I want

Hello,

I want my permalinks to be https://www.mydomain.com/blog/category/postname.

So I would think that I should put the following in the customized permalinks box: /%category%/%postname%/. However, when I do this, the links to my stories break.

The only thing that fixes them is to do this: /index.php/%category%/%postname%/. I do not want the index.php in there.

Anyone else seen this and/or know what I am doing wrong?

Thanks in advance. M.