O problema foi devido a um antigo pacote postgresql que de alguma forma foi colocado na lista negra da remoção. Como a atualização exigia que este pacote fosse desinstalado, mas não podia devido à lista negra, ele falhou, mas esse erro verdadeiro estava oculto nos logs e somente esse traceback do Python ficou imediatamente visível.
Remover manualmente o pacote e re-executar sudo do-release-upgrade
corrigiu o erro.
cat /var/log/dist-upgrade/main.log|less
...
Dist-upgrade failed: 'The package 'postgresql-9.4-postgis-2.1' is marked for removal but it is in the removal blacklist.'