Esta postagem parece ter a resposta: E: Não é possível localizar o pacote php5-imap
Parece que você precisa seguir a convenção de nomenclatura com a 5.6:
sudo apt-get install -y php5.6-imap
Então não esqueça de reiniciar o apache:
sudo systemctl restart apache2
Espero que ajude.