Eu peguei esse mesmo problema e o "consertei" fazendo downgrade para a versão do apt presente em 15.10.
No meu caso, fiz o seguinte:
sudo add-apt-repository 'deb http://archive.ubuntu.com/ubuntu wily-updates main'
sudo apt-get update # and ignore the errors
sudo aptitude install apt=1.0.10.2ubuntu2
E escolha a opção menos perturbadora. AVISO: a escolha de uma opção inválida pode remover pacotes importantes do sistema, continue com cautela.
Eu escolhi a seguinte opção:
The following actions will resolve these dependencies:
Remove the following packages:
1) libapt-inst2.0
2) libapt-pkg5.0
Install the following packages:
3) libapt-inst1.7 [1.0.10.2ubuntu2 (wily-updates)]
Downgrade the following packages:
4) apt-transport-https [1.2.10ubuntu1 (now, xenial) -> 1.0.10.2ubuntu2 (wily-updates)]
5) apt-utils [1.2.10ubuntu1 (now, xenial) -> 1.0.10.2ubuntu2 (wily-updates)]
6) aptitude [0.7.4-2ubuntu2 (now, xenial) -> 0.7.3-1ubuntu1.1 (wily-updates)]
7) aptitude-common [0.7.4-2ubuntu2 (now, xenial) -> 0.7.3-1ubuntu1.1 (wily-updates)]
8) python-apt [1.1.0~beta1build1 (now, xenial) -> 1.0.1ubuntu0.1 (wily-updates)]
9) python3-apt [1.1.0~beta1build1 (now, xenial) -> 1.0.1ubuntu0.1 (wily-updates)]
Leave the following dependencies unresolved:
10) libapt-pkg5.0 recommends apt (>= 1.2.10ubuntu1)
Accept this solution? [Y/n/q/?] Y