Eu tive o mesmo problema, como relatado aqui . Para ter um Tmate totalmente operacional, eu removo o repository on source-list.d
.
sudo rm -rf /etc/apt/sources.list.d/tmate_io-ubuntu-archive-artful.list*
E eles instalaram o Tmate normalmente.
sudo apt update
sudo apt install tmate
Como descrito na edição, o problema deve ser corrigido, mas isso funcionou para mim até agora.