Editar el archivo de configuracion
$sudo gedit /etc/apache2/sites-enabled/000-default
Cambiar las ocurrecias AllowOverride None por AllowOverride All
Reiniciar el servicio
$ sudo /etc/init.d/apache2 restart
Fuente: http://linuxandfriends.com/how-to-enable-mod_rewrite-in-ubuntu-linux/