Solución 1:
$ sudo apt-get install php5-cli
Debería hacerlo.
Solución 2:
Instalar php5 después php5-fpm si planea usar nginx por ejemplo, porque php5 necesita uno de los libapache2-mod-php5 , libapache2-mod-php5filter , php5-cgi o php5-fpm . Apt simplemente elige el primer paquete que satisface la dependencia.
$ sudo apt-get install php5-fpm php5