Consegui encontrar uma solução excluindo essa instância AWS defeituosa e implantando uma nova, novamente do Ubuntu Server 14.04, só que desta vez eu segui essas instruções para enviar o sendEmail: link
sudo apt-get install sendemail
sudo apt-get install libio-socket-ssl-perl
Eu assumo que meu problema era com o comando antigo que eu estava usando para instalar o perl5 antes (mas não sei ao certo, ou em caso afirmativo, por que):
apt-get install libio-socket-ssl-perl libnet-ssleay-perl perl