O problema aqui é que a versão do pacote 3.6.3-1+xenial2
foi considerada mais recente do que 3.6.3-1ubuntu1
.
A correção foi fazer o downgrade do pacote, mesmo que a versão real do Python fosse a mesma.
Esta foi uma questão estranha de se consertar, porque eu não tinha usado nenhum PPA que N0rbert sugerisse, e o pacote foi considerado mais recente que o dos repositórios principais (embora não tenha sido).
Isso pode ter ocorrido porque eu instalei este sistema pela primeira vez no Xenial, o que pode ter tido algo a ver com o motivo de eu ter instalado essa versão estranha. (Potencialmente um backport com esquema de nomenclatura diferente?)
Em pacotes de downgrade: Como rebaixar um pacote via apt-get