Why do I get 404 on LAMP Permalinks (Using wordpress)

Open a terminal and type:

sudo gedit /etc/apache2/apache2.conf

Find this:

<Directory /var/www/>

Change AllowOverride None to AllowOverride All

Then run:

sudo a2enmod rewrite

Dont forget to restart apache2:

sudo service apache2 restart