Tente executar uma atualização antes da instalação:
sudo apt-get update
Isto irá obter as informações sobre distribuições de pacotes.
Quando eu instalo o apache2 no meu Ubuntu, há um erro como este:
Reading package lists... Done
Building dependency tree
Reading state information... Done
E: Unable to locate package apache2-bin
Tente executar uma atualização antes da instalação:
sudo apt-get update
Isto irá obter as informações sobre distribuições de pacotes.