Uma das formas de remover todos os pacotes ligados ao PHP (por nome) de uma só vez, é:
apt-get purge `dpkg -l | grep php| awk '{print $2}' |tr "\n" " "`
Atenção: A opção purge remove completamente, incluindo as configurações. Caso queira preservar as configurações, basta alterar para “remove”.
Outra forma que parece funcionar para apt-get, mas não para o comando aptitude é:
apt-get purge php*