No momento da pergunta, o pacote PHP 5.5.25
foi quebrado no repositório.
Citação Comentário de Ondřej Surý à questão :
A equipe de launchpad do JFTR quebrou o tratamento de dependências alternativas (havia locales-all | language-pack-de antes) entre o php 5.5.24 e 5.5.25 [...].
Agradecimentos a hbdgaf , que gentilmente perguntou Ondřej Surý sobre isso no Launchpad , e obrigado a Ondřej Surý, que gentilmente corrigiu isso , citando a resposta de Ondřej Surý:
Adorável, launchpad quebrou as compilações.
Eu atualizei os pacotes para não dependerem de locales-all.
Felicidades, Ondrej
O pacote já está corrigido e você poderá instalá-lo usando sudo apt-get install --only-upgrade php5
.