$50 says you've changed your network configuration. This problem is normally symptomatic of the server's hostname being incorrectly changed. ensure that your local hostname is set in /etc/hosts
Code:
127.0.0.1 localhost localhost.localdomain kevslinuxbox
and restart sendmail. if that doesn't do it, there will be more detailed into added to the system log, /var/log/messages