add-apt-repository não é um pacote, então você não pode instalá-lo usando sudo apt-get install add-apt-repository . Isso está errado!
O pacote que contém o comando add-apt-repository é (e foi o tempo todo):
software-properties-common
não python-software-properties , como você pode pensar. Você pode verificar isso usando o seguinte comando:
dpkg -S add-apt-repository