Eu não acho que esse erro esteja relacionado diretamente ao laravel, mas sim ao seu ambiente.
Abra uma janela de terminal e digite:
sudo a2enmod rewrite
e sudo apache2ctl graceful
Isso garantirá que o módulo de reescrita esteja ativado e reinicie o servidor apache para garantir que o módulo esteja ativo.
Se isso não funcionar, você deve tentar isto:
sudo rm /etc/apache2/mods-enabled/rewrite.load
e sudo a2enmod rewrite
e sudo service apache2 restart