Eu estava tendo o mesmo problema, tentei executar o joomla instalando os pacotes LAMP básicos logo após o upgrade para o 16.04 quando isso começou a acontecer.
Não foi possível instalar nenhum pacote e não foi possível remover libapache2-mod-php5
Depois de algumas googleing e head scratching, imaginei que o fato de que o Apache ainda estava usando o php5 era parte do meu problema.
Não tenho certeza se essa foi a maneira correta de corrigir o problema, mas consegui corrigir isso fazendo o seguinte:
cd /etc/apache2/mods-enabled
sudo mv php5.conf php5.conf.old
sudo mv php5.load php5.load.old
sudo apt-get purge libapache2-mod-php5
sudo apt-get update
sudo apt-get upgrade
Isso resolveu e posso instalar e remover o software novamente.
Talvez alguém mais inteligente do que eu possa explicar por que isso funcionou ou apresenta uma solução mais elegante / apropriada.
De qualquer forma, espero que isso ajude.