Eu tive esse problema e tinha um pacote python-dodgy apt de outra fonte. Eu removi essas fontes de apt
manualmente editando /etc/apt/sources.list
e removendo arquivos de /etc/apt/sources.list.d
e depois fazendo:
apt-get update
apt-get remove python-apt
apt-get install update-manager-core
Este último irá reinstalar o python-apt, que deve vir das fontes apropriadas do ubtuntu. A atualização parece estar funcionando bem agora.