For those of you who are getting this issue and have tried every solution suggested at this forum to no avail (AllowOverride, chmod'ing htaccess, renaming htaccess, etc), hopefully this helps you.
It turns out my server (Ubuntu running apache) didn't have the mod_rewrite module enabled at all. The fix is simple:
1. Enable the module
sudo a2enmod rewrite
2. Confirm that AllowOverride in httpd.conf (or server equivalent) is set to "All"
3. Restart Apache
sudo /etc/init.d/apache2 restart
Once again, the above steps are for an Ubuntu box.
