I had the same problem of following the suggestions in the post and it not working on Ubuntu 10.04 running Apache2.
The additional step I had to take was to edit /etc/apache2/sites-enabled/000-default.
In that file you’ll find an AllowOverride setting for /var/www, saying “None”.
Change the setting to say: AllowOverride All
