Issue
Changing the WP PermaLink setting to postname causes a 404 error

Solution
Edit the
sudo nano /etc/apache2/apache2.conf
Change your apache config or add the following to it if its missing
<Directory /var/www/<yoursitefolder>>
Options Indexes FollowSymLinks
AllowOverride All
Require all granted
</Directory>
Restart the service
sudo service apache2 restart
Hits: 844