David,
I ran into similar problem before and I got sendmail working by
commenting out this line:
#localhost.localdomain RELAY
from the /etc/mail/access file. Then rebuild access.db by running
'make' from the /etc/mail directory. You may have to restart sendmail
to get it working.