If you find out references to the package python-software-properties everywhere, they are wrong.
For some reason the Ubuntu team decided to move add-apt-repository to a different package, and you need to install it explicitly. Just install:
sudo apt-get install software-properties-common