Depois de várias tentativas e cavando no google. Instalado sendmail + postfix várias vezes sem sucesso, tentei outras alternativas e nada também. Então eu encontrei este tutorial
Instalado apt-get install exim4-daemon-light mailutils
Configurado. E boom tudo começou a funcionar corretamente.
Enquanto eu estava brincando com o postfix, notei que ele não estava funcionando nem começando, e quando eu pedi para começar
postfix start
Ele estava emitindo fatal error: postfix failled to start
. Eu acho que foi por isso que não funcionaria. Obrigado pela sua atenção de qualquer maneira =)