Возможно надо проверить, подключен ли модуль mod_rewrite в Apache. Если подключен и работает, значит может быть в .htaccess что то не то
UPD: Насколько я понял, апач был только что установлен, но
mod_rewrite в апаче
не включен по умолчанию, надо самому включать. В терминале
a2enmod rewrite, и в конфиге /etc/apache2/apache2.conf поправить директорию /var/www
<Directory /var/www/>
Options Indexes FollowSymLinks Includes ExecCGI
AllowOverride All
Require all granted
</Directory>
и перезапустить сервер
sudo service apache2 restart
UPD: если проблема не в апаче, то попробуй в терминале выполнить 3 команды
php artisan cache:clear
php artisan route:clear
composer dump