Um ano após o seu post, eu tive o mesmo problema no Ubuntu 12.10
Eu descobri como contornar o problema (não para consertá-lo), então aproveito para postar uma resposta apenas para o registro. Nós nunca sabemos, se alguém enfrenta esse problema depois de mim.
O FIX (tipo de)
apt-get install software-properties-common
A explicação (tipo de)
It seems there is a dependancy issue on this package(s)
https://bugs.launchpad.net/ubuntu/+source/software-properties/+bug/1024408
Prova (tipo de)
You can see the python-software-properties doesn't include the
add-apt-repository binary :
dpkg -L python-software-properties
While the software-properties-common does :
dpkg -L software-properties-common