AllowOverride All solution works fine for me. Here is what I did:

1) sudo a2enmod rewrite
2) sudo nano -w /etc/apache2/sites-enabled/000-default