Eu estava com o mesmo problema, consegui resolver.
Resolvi da seguinte forma:
Habilitando o módulo rewrite.load no Apache
$ sudo a2enmod rewrite
Alterando o arquivo de configuração do Apache
$ sudo nano /etc/apache2/apache2.conf
Encontre o seguinte código:
<Directory /var/www/>
Options Indexes FollowSymLinks
AllowOverride None
Require all granted
</Directory>
Altere para:
<Directory /var/www/>
Options Indexes FollowSymLinks
AllowOverride All
Require all granted
</Directory>
Reinicializar o servidor Apache.
$ sudo /etc/init.d/apache2 restart