O problema é que, de alguma forma, eu acidentalmente configurei o servidor para usar um kernel muito antigo, mesmo que os mais recentes tenham sido instalados. A solução foi reinicializar, e na tela de inicialização do Grub, assegure que o kernel mais recente foi selecionado, o que para mim era 3.13.
Isso me permitiu concluir a atualização corrigindo a instalação da libc6 e executando todas as outras atualizações, incluindo a instalação do pacote padrão do kernel Xenial, que me levou a um kernel 4.4.