Host migrated to new servers recently. Couldn't access my wp-admin after my server was done (this w/ old version of the plugin). They sent me this email after doing some work..
We've corrected the .htaccess file in the 'wp-admin/' directory. It appears you had some references to disable the mod_security engine for this directory and we recently upgraded our servers to mod_sec2 so these directives no longer work properly. I've commented them out and the login page is now loading properly.
Then I had to deactivate the plugin later for some reason and got a 404 error on every site page but my main page. I could still access my admin panel just fine.
Put my site into maintenance and phoned tech support. I think they essentially tweaked/reversed what the others did. Upgraded the plugin, re-activated, and failed the test in a number of spots.
Took a couple screenshots and am sending these over to tech support. I hope to hear back on why the server doesnt work with the plugin and if so, I'll report back here...by the way I use Hostgator.