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
3) Change AllowOverride None to AllowOverride all
4) Restart Apache: sudo /etc/init.d/apache2 force-reload