Eu resolvi esse problema (também causado pela alteração de ppa de python3.6 de jonathonf para deadsnakes) removendo python3-tk (que é o pacote "antigo" python3.6 do jonathonf ppa).
sudo apt remove python3-tk
Também não tenho certeza se isso me ajudou, mas eu limpei /usr/lib/python3.6/
após remover (python3.6, python3.6-minimal, libpython3.6-stdlib e apt autoremove)