I am having the same problem now also. My custom Permalink structure is “/index.php/%postname%/” If I change to use the default Permalink, everythign works great. Anytime I change to one of the other permalinks, I receive the 404 errors.
What other options are there, other than downgrading?
– Brendan