Você se lembrou de reiniciar o apache depois de adicionar o
<Directory /var/www/>
AllowOverride All
</Directory>
para sua configuração? A única maneira de reproduzir o que você vê é fazer isso. Assim que eu reiniciar o apache, tudo começa a funcionar como esperado.
EDIT: com base nos comentários, parece que as diretivas acima foram adicionadas ao arquivo errado. Eles foram adicionados ao /etc/apache2/apache.conf
em vez do arquivo /etc/apache2/sites-enabled/000-default
.