O software-properties-common é buggy, portanto, se tiver tempo, relate isso como um bug em propriedades de software comuns.
Uma melhor solução foi apontada no rastreador de problemas que usa um código de idioma unicode específico ao adicionar o repositório
LC_ALL=C.UTF-8 add-apt-repository -y ppa:ondrej/php5-5.6