Corrigido com rm -rf /etc/apt/trusted.gpg.d/*
Aparentemente, o gpg de algum repositório antigo estava bagunçando as coisas, apesar de esses repositórios estarem desativados.
apt-get update após a atualização - recebo a seguinte mensagem
W: GPG error: http://archive.canonical.com/ubuntu xenial InRelease: At least one invalid signature was encountered.
W: The repository 'http://archive.canonical.com/ubuntu xenial InRelease' is not signed.
N: Data from such a repository can't be authenticated and is therefore potentially dangerous to use.
N: See apt-secure(8) manpage for repository creation and user configuration details.
W: GPG error: http://ua.archive.ubuntu.com/ubuntu xenial InRelease: At least one invalid signature was encountered.
W: The repository 'http://ua.archive.ubuntu.com/ubuntu xenial InRelease' is not signed.
N: Data from such a repository can't be authenticated and is therefore potentially dangerous to use.
N: See apt-secure(8) manpage for repository creation and user configuration details.
W: GPG error: http://ua.archive.ubuntu.com/ubuntu xenial-security InRelease: At least one invalid signature was encountered.
W: The repository 'http://ua.archive.ubuntu.com/ubuntu xenial-security InRelease' is not signed.
N: Data from such a repository can't be authenticated and is therefore potentially dangerous to use.
N: See apt-secure(8) manpage for repository creation and user configuration details.
W: GPG error: http://ua.archive.ubuntu.com/ubuntu xenial-updates InRelease: At least one invalid signature was encountered.
W: The repository 'http://ua.archive.ubuntu.com/ubuntu xenial-updates InRelease' is not signed.
N: Data from such a repository can't be authenticated and is therefore potentially dangerous to use.
N: See apt-secure(8) manpage for repository creation and user configuration details.
W: GPG error: http://ua.archive.ubuntu.com/ubuntu xenial-proposed InRelease: At least one invalid signature was encountered.
W: The repository 'http://ua.archive.ubuntu.com/ubuntu xenial-proposed InRelease' is not signed.
N: Data from such a repository can't be authenticated and is therefore potentially dangerous to use.
N: See apt-secure(8) manpage for repository creation and user configuration details.
W: GPG error: http://ua.archive.ubuntu.com/ubuntu xenial-backports InRelease: At least one invalid signature was encountered.
W: The repository 'http://ua.archive.ubuntu.com/ubuntu xenial-backports InRelease' is not signed.
N: Data from such a repository can't be authenticated and is therefore potentially dangerous to use.
N: See apt-secure(8) manpage for repository creation and user configuration details.
Tentei
sudo apt-get clean
sudo mv /var/lib/apt/lists /tmp
sudo mkdir -p /var/lib/apt/lists/partial
sudo apt-get clean
sudo apt-get update
Isso não ajudou.
Minha lista de fontes atual:
###### Ubuntu Main Repos
deb http://ua.archive.ubuntu.com/ubuntu/ xenial main restricted universe multiverse
###### Ubuntu Update Repos
deb http://ua.archive.ubuntu.com/ubuntu/ xenial-security main restricted universe multiverse
deb http://ua.archive.ubuntu.com/ubuntu/ xenial-updates main restricted universe multiverse
deb http://ua.archive.ubuntu.com/ubuntu/ xenial-proposed main restricted universe multiverse
deb http://ua.archive.ubuntu.com/ubuntu/ xenial-backports main restricted universe multiverse
###### Ubuntu Partner Repo
deb http://archive.canonical.com/ubuntu xenial partner
Corrigido com rm -rf /etc/apt/trusted.gpg.d/*
Aparentemente, o gpg de algum repositório antigo estava bagunçando as coisas, apesar de esses repositórios estarem desativados.