Acabou sendo um problema com uma das fontes. Especificamente, removendo esta linha de /etc/apt/sources.list
corrigiu: deb [arch=amd64] https://download.docker.com/linux/ubuntu xenial stable
.
Depois disso, executei o clean, autoclean e segui o guia que adicionou a mesma fonte novamente após o ponto em que continuou trabalhando.
Espero que isso seja útil se alguém encontrar o mesmo problema.