Возможно, модуль перезаписи не установлен на вашем сервере Apache. Попробуйте это в командной строке с Debian:
ln -s /etc/apache2/mods-available/rewrite.load /etc/apache2/mods-enabled/rewrite.load
Или это с Ubuntu:
sudo ln -s /etc/apache2/mods-available/rewrite.load /etc/apache2/mods-enabled/rewrite.load