postname permalinks not working

Moving from a shared host to a VPS has been an awesome experience except for one thing. The postname permalink is not working. All pages and posts except for home page gives me a 404 error. The Default works fine and if I add index.php before postname it works aswell.

I am on Ubuntu 14.04 LTS L.A.M.P, Apache2 installed. Using wordpress 4.1

But obviously I don’t want that. There are a lot of threads about this problem but none of the solutions I’ve found seems to work. Here is what I’ve tried:

– Making sure mod_rewrite is installed by using “sudo a2enmod rewrite” and it returns:
“Module rewrite already enabled”

– Made sure my .htaccess file is correct:

# BEGIN WordPress
<IfModule mod_rewrite.c>
RewriteEngine On
RewriteBase /
RewriteRule ^index\.php$ – [L]
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule . /index.php [L]
</IfModule>
# END WordPress
`

– I’ve made sure that my /etc/apache2/sites-enabled/000-default.conf has the following lines:

ServerAdmin webmaster@localhost
DocumentRoot /var/www/html
<Directory /var/www/html”>
AllowOverride All
</Directory>

– I’ve tried restarting the server after all changes.

– I’ve tried changing permissions on .htaccess to 666

– I’ve tried disabling all plugins and switched to Fifteen Twenty theme

I am losing my mind here and would really appreciate all the help I can get.