A desclassificação de pacotes é um problema muito difícil. Você deve usar ppa-purge para isso. Mas ppa-purge requer que o PPA ainda seja adicionado, então você terá que adicionar de volta o PPA, e então usá-lo.
Eu adicionei o repositório de Ondřej Surý, que foi uma grande ajuda na época. Agora eu tenho problemas ao instalar o cURL e acho que retornar ao PHP "original" resolveria o problema.
Atualmente todos os meus pacotes PHP são do repositório DEB.SURY.ORG.
ii php5 5.5.12+dfsg-2+deb.sur all
ii php5-cli 5.5.12+dfsg-2+deb.sur amd64
ii php5-common 5.5.12+dfsg-2+deb.sur amd64
ii php5-gd 5.5.12+dfsg-2+deb.sur amd64
ii php5-imagick 3.1.2-1+debphp.org~pr amd64
ii php5-json 1.3.4-3+deb.sury.org~ amd64
rc php5-mcrypt 5.5.8+dfsg-3+sury.org amd64
ii php5-mysql 5.5.12+dfsg-2+deb.sur amd64
Já removi o arquivo .list do Ondřej.
Como posso voltar aos pacotes php originais, causando interrupções mínimas para os meus usuários?