Did you restarted Apache after enabling?
When you tried to enabled rewrite, did you used sudo if you use non-root user?

sudo a2enmod rewrite

This is correct output of command:

Correct output - a2enmod rewrite
Enabling module rewrite.
To activate the new configuration, you need to run:
  service apache2 restart

As it said, it requires Apache to be restarted:

sudo service apache2 restart

If you have some other output for a2enmod please post it here.

This message usually shows if you don’t have rewrite enabled.