mail
aponta para uma das alternativas.
ls -l /usr/bin/mail
lrwxrwxrwx 1 root root 22 Jan 5 2011 /usr/bin/mail -> /etc/alternatives/mail
ls -l /etc/alternatives/mail
lrwxrwxrwx 1 root root 18 Jan 5 2011 /etc/alternatives/mail -> /usr/bin/bsd-mailx
Você provavelmente estava usando outro programa de e-mail no passado. Tente descobrir qual era.
Depois de ter instalado o pacote correto, altere a alternativa assim:
sudo update-alternatives --config mail