As etapas listadas no link são exatamente o que eu precisava. Eu fiz uma nova instalação do Ubuntu, corri
sudo tasksel install lamp-server
e, em seguida, seguiu as etapas na seção Solução de problemas, por exemplo
apt-get --purge remove php5-common apt-get install php5 phpmyadmin