I tested in a live Ubuntu 16.04.1 LTS and I get ppa:ondrej/php without problems.
But there was a warning, that might explain your problem: "add -apt-repository is broken with non-UTF-8 locales, see github.com/oerdnj/deb.sury.org/issues/56 for workaround"
[my comment: Scroll and you will see the following code, that you can try.]
apt-get update &&
apt-get install -y language-pack-en-base &&
export LC_ALL=en_US.UTF-8 &&
export LANG=en_US.UTF-8 &&
apt-get install -y software-properties-common &&
add-apt-repository -y ppa:ondrej/php5-5.6 &&
add-apt-repository -y ppa:ondrej/mariadb-10.0 &&
apt-get update &&
apt-get -y upgrade
If that does not work, read the link carefully and look for other tips and tricks.
sudo apt update && sudo apt dist-upgrade