Permalink Problem

I am having a problem with my permalinks,

I tried to change the permalink structure to a custom structure of:
/%year%/%monthnum%/%day%/%postname%/

Basically, just removing the /index.php/ section at the start of the permalink.

So for example a post with the old structure had the permalink:

https://www.stockdisplays.co.uk/blog/index.php/2010/03/04/new-post/

The new structure I want would be:

https://www.stockdisplays.co.uk/blog/2010/03/04/new-post/

I have changed the structure, but all of the new permalinks are now not working – can anybody explain why this is so?

Thanks,

Dan.