.htaccess not working even though allowoverride is enabled
For what it's worth, I had a very similar problem with Ubuntu Server 11.10 and LAMP. I had to run the command
sudo a2enmod rewritewhich did the trick for me. Maybe it's the solution for you or some other people coming in here.