Teddy, can you provide us access to your site to troubleshoot? if that works, lets start with a temp wp admin account with sp admin capabilities… if doable, please pm them to yellow swordfish and mr papa with a link to this topic… depending on what we find, we may ask for ftp access…
it appears that your site is using pathinfo permalinks… can you verify that this is enforced by the server? or are you actually choosing to have the index.php in the permalink? (we could determine this ourselves with access)…
if wp did make a change to pathinfo style permalinks, we cannot really test since its very hard to simulate that setup not at the server level…