Verifique suas fontes do apt. Você deve ter este arquivo:
/etc/apt/sources.list.d/ondrej-php-trusty.list
Se você não fizer isso, adicione da seguinte forma:
sudo add-apt-repository ppa:ondrej/php
sudo apt-get update
sudo apt-get upgrade
Se você tiver alguma dependência quebrada, verifique este post para mais detalhes.
Se você acabar seguindo isso, apenas observe que onde eles sugerem que você use o comando ln -sfn para mudar as versões do php, você realmente deveria estar usando:
update-alternatives --config php