I was messing with the hotlink protection in CPanel, and just toggled it on and off, unfortunately this broke the permalinks in wordpress. Specifically it removed the line:

RewriteEngine On

In .htaccess

Took me a while to track down.

With wp-supercache, the mod_rewrite part of your .htaccess should look like:

<IfModule mod_rewrite.c>
# BEGIN WordPress

RewriteEngine On
RewriteBase /
#RewriteCond %{QUERY_STRING} !.*s=.*
#RewriteCond %{HTTP_COOKIE} !^.*comment_author_.*$
#RewriteCond %{HTTP_COOKIE} !^.*wordpress.*$
#RewriteCond %{HTTP_COOKIE} !^.*wp-postpass_.*$
#RewriteCond %{HTTP:Accept-Encoding} gzip
#RewriteCond %{DOCUMENT_ROOT}/wp-content/cache/supercache/%{HTTP_HOST}/$1/index.html.gz -f
#RewriteRule ^(.*) /wp-content/cache/supercache/%{HTTP_HOST}/$1/index.html.gz [L]

#RewriteCond %{QUERY_STRING} !.*s=.*
#RewriteCond %{HTTP_COOKIE} !^.*comment_author_.*$
#RewriteCond %{HTTP_COOKIE} !^.*wordpress.*$
#RewriteCond %{HTTP_COOKIE} !^.*wp-postpass_.*$
#RewriteCond %{DOCUMENT_ROOT}/wp-content/cache/supercache/%{HTTP_HOST}/$1/index.html -f
#RewriteRule ^(.*) /wp-content/cache/supercache/%{HTTP_HOST}/$1/index.html [L]
#
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule . /index.php [L]

# END WordPress
</IfModule>

In my case the “RewriteEngine On” was missing, causing individual pages not to work, but the main page worked fine, so I did not notice.