Web Developer, PHP, Drupal, Symfony.

verifique se o arquivo do módulo existe em:

ubuntu 8.04:
ls /usr/lib/apache2/modules/mod_rewrite.so
ubuntu 9.04:
ls /etc/apache2/mods-available/rewrite.load

se existir então ative com o comando:

sudo a2enmod rewrite

se tudo deu certo você receberá uma mensagem do tipo:

nei@terra:/usr/lib/apache2/modules$ sudo a2enmod rewrite
Enabling module rewrite.
Run '/etc/init.d/apache2 restart' to activate new configuration!

e pronto!