Well, is sendmail running? Can you connect via telnet to localhost port 25? What if you try to send mail on the command line using the sendmail binary?
$ echo "To: [email]me@example.com[/email]
From: [email]i@example.com[/email]
Subject: Test
This is a test.
" | sendmail -t -i
Anything in the mail log? (For postfix, debian has the mail log at /var/log/mail.log. Not sure what they do for sendmail.)