I had a similar issue, but on a vanilla wordpress install because I actually hadn’t generated .htaccess yet. What worked for me is changing the permalink structure with pages added (but wp-cache off), changing the permalink structure back, then re-enabling wp-cache. It’s worth a try, since permalinks rely directly on mod_rewrite in order to work.
