First of all, rule out the possibility of firewalls blocking access. This is the most common cause for problems.
Then check your "/etc/hosts.allow" and "/etc/hosts.deny" files. Under normal circumstances you'll want anyone to be able to access sendmail.
Finally, verify that the file "/etc/mail/sendmail.mc" contains a line "Djdomain.com" where "domain.com" is replaced with the official domain name of your mail server.