I had this issue today after migrating a WordPress website to a new server using backupbuddy and wanted to post the quick solution here in case it might help anyone else as it did me. It can sometimes take hours to solve simple problems like this. This fix applies to apache2 servers that won't work with WordPress permalinks when they are set to something like "Post Name" as mine were. I'll post two simple solutions that will fix most situations when this happens:

Save Permalinks

The first thing you want to try is simply going to wp-admin and clicking on "settings/permalink" and selecting the correct setting if not selected already and clicking the "Save Settings" button to re-save the settings(even if they were correct), Then refresh the page where links failed before and try them again. If that didn't work and you are on a Apache or Apache2 server, move on to the next fix below.

Edit Config File

Next try going to etc/sites-available and find the file named after your site which will look something like example.com.conf and open it for editing either using VI editor from command line or by downloading to your desktop and editing with note pad. My file that failed to work had the following content:

<Directory /var/www/html/dev.jafty.com/public_html>
    Require all granted
</Directory>
<VirtualHost *:80>
    ServerName dev.jafty.com
    ServerAlias www.dev.jafty.com

    ServerAdmin webmaster@localhost
    DocumentRoot /var/www/html/dev.jafty.com/public_html

    ErrorLog /var/www/html/dev.jafty.com/logs/error.log
    CustomLog /var/www/html/dev.jafty.com/logs/access.log combined
</VirtualHost>

The problem was right up at the top where you see the line:

      Require all granted

I simply added the following two lines above that one line and saved it to my server then restarted the server from command prompt with:"service apache2 restart" and the permalinks began working! Here are the two lines to add above "Require all granted":

        Options Indexes FollowSymLinks MultiViews
        AllowOverride All

Then simply save the file and restart your server and try permalinks again and they should work! The final .conf file should look like this:

<Directory /var/www/html/dev.jafty.com/public_html>
        Options Indexes FollowSymLinks MultiViews
        AllowOverride All
        Require all granted
</Directory>
<VirtualHost *:80>
    ServerName dev.jafty.com
    ServerAlias www.dev.jafty.com

    ServerAdmin webmaster@localhost
    DocumentRoot /var/www/html/dev.jafty.com/public_html

    ErrorLog /var/www/html/dev.jafty.com/logs/error.log
    CustomLog /var/www/html/dev.jafty.com/logs/access.log combined
</VirtualHost>

Hope that helps! Good Luck!