Obrigado a @douggro que encontrou a resposta.
Encontre o id do processo do Apache2 com:
pidof apache2
Mate o (s) processo (s):
sudo kill -9 <pid>
Então você pode iniciar o Apache2 normalmente:
sudo service apache2 start
UPDATE
Se sudo kill -9 <pid>
não funcionar, tente sudo kill <pid>
!