Check to make sure you have mod_rewrite enabled.

Under Apache 2+

sudo a2enmod rewrite && sudo service apache2 restart

or

sudo a2enmod rewrite && sudo /etc/init.d/apache2 restart