First, the WordPress folder wasn’t writable by the www-user.
Secondly, this needed to be done:
You have to edit the Apache conf file (in Ubuntu 14.04: /etc/apache2/apache2.conf) and change the AllowOverride setting from None to FileInfo
Options Indexes FollowSymLinks
Require all granted
You may need to enable the Rewrite module:
sudo a2enmod rewrite