I've seen similar posts but no solution. If this hasn't been fixed, perhaps this will help?
If my link looks like this then it will work:
If I change the permalink to eliminate index.php then I get a WordPress 404 error:
[and yes, htaccess is redirecting ok]
I found a link to what was supposed to be a fixed copy of classes.php, but it appears that the problem is still there in the version that I downloaded.
I put some debug code into classes.php and in the function parse_request() I find the following situation right before the comment that says "// The requested permalink is in $pathinfo for path info requests and in $req_uri for other requests"
Using index.php $pathinfo = 2006/01.. $requri = index.php
Without index.php $pathinfo = (blank) $requri = 2006/01..
A few lines later in the code, the value of $request in both cases is 2006/01/13/hello-world so it would seem that they both should have the same result.
However, when using index.php I notice a few lines later that the if statement with the comment "// If the requesting file is the anchor of the match, prepend it..." is executed and $request_match now contains the value index.php/2006/01.. while in the non-working case it remains the same as $request.
(By the way, why is the if statement in the while loop? It executes multiple times)
In any event, if $request_match contains "index.php" the permalink works and without it the 404 comes up.