O Ubuntu 16.04 removeu pacotes php5 e removeu aqueles com pacotes do PHP 7.0 que não possuem o php5, mas apenas o php dentro dos nomes dos pacotes, então substitua o comando por:
sudo apt-get install php libapache2-mod-php php-mysql php-curl php-gd php-intl php-pear php-imagick php-imap php-mcrypt php-memcache php-ming php-ps php-pspell php-recode php-sqlite php-tidy php-xmlrpc php-xsl
Similar pergunta aqui: PHP e Apache2 quebrados após atualizar para o Ubuntu 16.04 ou PHP renderizado como texto após Upgrade do Ubuntu 16.04