Eu tive o mesmo problema. Depois de pesquisar muito descobri que o caminho de @Doug Smythies funciona perfeitamente para mim. Até voto.
Então eu vou para o terminal e corro o seguinte código:
sudo a2enmod rewrite
sudo service apache2 restart
E é isso. Espero que isso ajude os outros.