After fresh installs I always come across this error message and need to fix it.
You can either install python-software-properties or add the entry manually at /etc/apt/sources.list
sudo apt-get install python-software-properties
Related External Links: