Comment 92 for bug 1573206

I found that SOME repositories don't have the package files for Gnome updates, but some others do. So for me the same symptoms occurred with Gnome updates.

Changing my local repository to another one fixed the problem for me. In my case adding deb http://fr.archive.ubuntu.com/ubuntu xenial-updates main solved the problem.

Here's a list of mirrors I think work at least with gnome updates:

http://packages.ubuntu.com/xenial-updates/all/gnome-software-common/download