Vous avez le mauvais PPA. Voir ce lien :
Versions de PHP co-installables : PHP 5.6, PHP 7.0, PHP 7.1 et les extensions les plus demandées sont incluses.
N'UTILISEZ PAS PHP 5.4 OU PHP 5.5. Les versions PHP 5.5 et ultérieures ne sont plus supportées par les mises à jour de sécurité, elles ne sont donc pas incluses dans ce référentiel.
Il semble que vous ayez besoin d'utiliser...
sudo add-apt-repository ppa:ondrej/php
sudo apt-get update
Notez également que PHP 5.6 ou plus n'est pas supporté par apache en dessous de la version 2.4 et que la version 2.4 n'est pas supportée par la version 12.04. Vous devrez également mettre à jour apache si vous ne l'avez pas encore fait.