Experimente sudo apt-get remove lamp-server^ --simulate
Se isso parecer com o que você deseja, remova o --simulate flag e realmente faça a desinstalação.
Uma variação disso, segmentando pacotes relevantes manualmente, seria da seguinte maneira:
sudo apt-get --simulate remove mysql-server apache2 php5 libapache2-mod-php5 openssh-server openssl
Se houver outros pacotes que dependem de coisas como mysql que você deseja manter, esse pode ser o melhor caminho a seguir. Novamente, remova --simulate para executar o comando. (Com apt-get , -s é equivalente a --simulate e você provavelmente o usaria no trabalho do dia-a-dia.)
Para o problema tasksel e aptitude em particular, você pode tentar sudo apt-get autoclean e sudo apt-get clean para ver se isso elimina o erro.