De suas saídas, parece-me que suas fontes não estão completas e é por isso que apt
reclama de alguns pacotes que não serão instalados.
Adicione estas duas linhas:
deb http://archive.ubuntu.com/ubuntu xenial-updates main restricted universe multiverse
deb http://security.ubuntu.com/ubuntu xenial-security main universe multiverse
para /etc/apt/sources.list
e, em seguida, execute:
sudo apt update
Agora tente novamente instalar pacotes removidos recentemente. Deve funcionar agora.
Você também pode dar uma olhada em /var/log/apt/history.log
para ver quais pacotes foram removidos com o comando remove
.