apt-get broken: No module named debian.deb822
Try reinstalling the package which is supposed to contain debian.deb822:
sudo apt-get --reinstall install python-debian
In my case I had to uninstall all conflicting packages like update-notifier, update-notifier-common, etc and then I ran:
sudo apt install --reinstall python-debian python3-debian python-chardet python3-chardet