Eu estava usando o repositório ppa: ondrej / php5 para ter o php 5.4 rodando em 12.04LTS.
Acontece que eles atualizaram o PHP de 5.4.x para 5.5.x, que parece precisar do Apache 2.4, enquanto eu tinha 2.2. Eu tentei atualizar o Apache através de outro repositório, e então foram alguns recursos necessários ao Virtualmin que eram incompatíveis com o Apache 2.4.
Então eu desinstalei o PHP e o Apache, removi os 2 repositórios e adicionei o ppa: ondrej / php5-oldstable, que é a versão 5.4 e continuará assim. Veja link
Funciona bem agora.