Ok, it turns out that on ubuntu/debian, the wordpress files are in 3 places on the filesystem – /var/lib/wordpress, /srv/www/wp-content and /usr/share/wordpress. I had to do this for all three:
sudo chown -R www-data .
sudo chgrp -R www-data .
sudo find . -type f -exec chmod 644 {} \;
sudo find . -type d -exec chmod 755 {} \;
Works fine now. Even installation through the dashboard works now.