Primeiro você deve procurar pelo pacote:
apt-cache search apache
aptitude search apache .
No entanto, o apache2 é o pacote correto. Você deve fazer um sudo apt-get update e, se não corrigir, verifique seu /etc/apt/sources.list . (Poste no pastebin.com e nos forneça o link se você não conseguir descobrir.)