When you include index.php/ at the start of your custom permalink structure you are telling WordPress to use PATHINFO permalinks.
WordPress Codex – PATHINFO: “Almost_Pretty”
It is possible you are using an IIS (Windows) server or that mod_rewrite is not working correctly. Permalinks without mod_rewrite
The following plugin can help you determine if mod_rewrite is working correctly or if it is not available.
Rewriterule Viewer Plugin