I tried all of the solutions posted here and none of them worked. What finally fixed it was two things. Please keep in mind that this is with a self-installed Ubuntu 8.10 server running LAMP
- Having AllowOveride set to all in my virtual host config
- And running the following command
sudo a2enmod rewrite
That command was found Here
