Si se trata de una instalación nueva del servidor web, es posible que las reglas .htaccess no estén permitidas de forma predeterminada. Para arreglar eso, edite su httpd.conf (usualmente está en /etc/apache2), busque
<Directory "path/to/your/document/root">
# ....
AllowOverride None
# ....
</Directory>
y cambiar
AllowOverride None
a
AllowOverride All
Luego reinicie su servidor web y vuelva a intentarlo.