I think hackers have found a way to cause a 404 error to be returned and then captured by the cache and served up from then on.. I had all my pages showing as 404s and I couldn't figure it out (menus were fine and the pages were all published and I republished a few and I still would get the error when I viewed the page.
I deactivated all plugins and restarted them a few at a time. Now all pages are working again but your plugin is turned on but as of a few hours later, it's not causing any problems.
I have been noticing a lot of 404 errors in my security software (hundreds) and didn't know why but maybe there is a linkage between these issues