In addition to Mike's answer about editing /etc/mail/sendmail.mc, it's worthwhile mentioning netstat and lsof as general-purpose diagnostic tools:
# to discover on what tcp ports we're listening netstat -tl
# to discover to what ports sendmail is bound lsof -iTCP -n | grep sendmail
The output of these tools won't tell you how to fix the problem, but they might give you a better glimpse into the problem's nature. In this case, you'd have discovered that sendmail was only bound to the loopback interface.