Como mencionado nos comentários, apenas a alteração de substituições não é suficiente para permitir a reescrita de URL - você terá que ativar o módulo de reconfiguração.
Você pode fazer isso digitando
sudo a2enmod rewrite
e reinicie o serviço Apache
sudo service apache2 restart
Isso deve fazer o truque.