Have you futzed with /etc/mail/access? It must contain at least:

# by default we allow relaying from localhost...
localhost.localdomain           RELAY
localhost                       RELAY
127.0.0.1                       RELAY
                                                                               
Are both sendmail instances running? Like:

chaos> ps -ef | grep sendmail | grep -v grep
root      5112     1  0 Feb13 ?        00:00:00 sendmail: accepting connections
smmsp     5121     1  0 Feb13 ?        00:00:00 sendmail: Queue runner@01:00:00 for /var/spool/clientmqueue

Is there a firewall running on the box that might be blocking access to the localhost IP? The RedHat firewall won't but if you've made this into a gateway you might have accidentally blocked access to 127.0.0.1

An example of doing that would be to use a default stance of deny for the INPUT chain, like:

iptables  -P INPUT DROP

and failing to include a rule to permit localhost traffic, like:

iptables -A INPUT -i lo -j ACCEPT

The firewall rule set that I use on a gateway is below. It's pretty heavily commented, quite secure, and easily modifed for local conditions. At the least you might find it an interesting read.

 #!/bin/sh
#
# Save this in root's home directory as iptables-gw and make it executable
# with 'chmod +x iptables-gw'. Then to install the rule set simply run it
# with './iptables-gw'.

# For a system to function as a firewall the kernel has to be told to forward
# packets between interfaces, i.e., it needs to be a router. Since you'll save
# the running config with 'iptables save' for RedHat to reinstate at the next
# boot IP fordarding must be enabled by other than this script for production
# use. That's best done by editing /etc/sysctl.conf and setting:
#
# net.ipv4.ip_forward = 1
#
# Since that file will only be read at boot, you can uncomment the following
# line to enable forwarding on the fly for initial testing. Just remember that
# the saved iptables data won't include the command.
#
#echo 1 > /proc/sys/net/ipv4/ip_forward
#
# Once the rule sets are to your liking you can easily arrange to have them
# installed at boot on a Redhat box (7.1 or later). Save the rules with:
#
# service iptables save
#
# which saves the running ruleset to /etc/sysconfig/iptables. When
# /etc/init.d/iptables executes it will see the file and restore the rules.
# I find it easier to modify this file and run it to change the rulesets.,
# rather than modifying the running rules. That way I have a readable record
# of the firewall configuration.
#
# Set an absolute path to IPTABLES and define the interfaces.
#
IPT="/sbin/iptables"
#
# OUTSIDE is the outside or untrusted interface that connects to the Internet
# and INSIDE is, well that ought to be obvious.
#
OUTSIDE=eth1
INSIDE=eth0
INSIDE_IP=10.0.0.254
#
# Clear out any existing firewall rules, and any chains that might have
# been created. Then set the default policies.
#
$IPT -F
$IPT -F INPUT
$IPT -F OUTPUT
$IPT -F FORWARD
$IPT -F -t mangle
$IPT -F -t nat
$IPT -X
$IPT -P INPUT DROP
$IPT -P OUTPUT ACCEPT
$IPT -P FORWARD ACCEPT
#
# Begin setting up the rulesets. First define some rule chains to handle
# exception conditions. These chains will receive packets that we aren't
# willing to pass. Limiters on logging are used so as to not to swamp the
# firewall in a DOS scenario.
#
# silent       - Just dop the packet
# tcpflags     - Log packets with bad flags, most likely an attack
# firewalled   - Log packets that that we refuse, possibly from an attack
#
$IPT -N silent
$IPT -A silent -j DROP

$IPT -N tcpflags
$IPT -A tcpflags -m limit --limit 15/minute -j LOG --log-prefix TCPflags:
$IPT -A tcpflags -j DROP

$IPT -N firewalled
$IPT -A firewalled -m limit --limit 15/minute -j LOG --log-prefix Firewalled:
$IPT -A firewalled -j DROP
#
# Use  NPAT if you have a dynamic IP. Otherwise comment out the following
# line and use the Source NAT below.
#
$IPT -t nat -A POSTROUTING -o $OUTSIDE -j MASQUERADE
#
# Use Source NAT to do the NPAT you have a static IP or netblock.
# Remember to change the IP to be that of your OUTSIDE NIC.
#
#$IPT -t nat -A POSTROUTING -o $OUTSIDE -j SNAT --to 1.2.3.4
#
# To Statically NAT an outside IP (1.2.3.4) to an inside IP (10.0.0.2) you'd
# do something like:
#
#$IPT -t nat -A PREROUTING -i $OUTSIDE -d 1.2.3.4 -j DNAT --to-destination 10.0.0.2
#$IPT -t nat -A POSTROUTING -o $OUTSIDE -s 10.0.0.2 -j SNAT --to-source 1.2.3.4
#
# These are all TCP flag combinations that should never, ever, occur in the
# wild. All of these are illegal combinations that are used to attack a box
# in various ways.
#
$IPT -A INPUT -p tcp --tcp-flags ALL FIN,URG,PSH -j tcpflags
$IPT -A INPUT -p tcp --tcp-flags ALL ALL -j tcpflags
$IPT -A INPUT -p tcp --tcp-flags ALL SYN,RST,ACK,FIN,URG -j tcpflags
$IPT -A INPUT -p tcp --tcp-flags ALL NONE -j tcpflags
$IPT -A INPUT -p tcp --tcp-flags SYN,RST SYN,RST -j tcpflags
$IPT -A INPUT -p tcp --tcp-flags SYN,FIN SYN,FIN -j tcpflags
#
# Allow selected ICMP types and drop the rest.
#
$IPT -A INPUT -p icmp --icmp-type 0 -j ACCEPT
$IPT -A INPUT -p icmp --icmp-type 3 -j ACCEPT
$IPT -A INPUT -p icmp --icmp-type 11 -j ACCEPT
$IPT -A INPUT -p icmp --icmp-type 8 -m limit --limit 1/second -j ACCEPT
$IPT -A INPUT -p icmp -j firewalled
#
# We've slipped the surly bonds of windows and are dancing on the
# silvery wings of Linux, so don't allow that windows broadcast trash
# to leak out of the firewall.
#
$IPT -A FORWARD -p udp --dport 137 -j silent
$IPT -A FORWARD -p udp --dport 138 -j silent
$IPT -A FORWARD -p udp --dport 139 -j silent
$IPT -A FORWARD -p udp --dport 445 -j silent
#
# Examples of Port forwarding.
#
# The first forwards HTTP traffic to 10.0.0.10
# The second forwards SSH to 10.0.0.10
# The third forwards a block of tcp and udp ports (2300-2400) to 10.0.0.10
#
# Remember that if you intend to forward something that you'll also
# have to add a rule to permit the inbound traffic.
#
#$IPT -t nat -A PREROUTING -i $OUTSIDE -p tcp --dport 80 -j DNAT --to 10.0.0.10
#$IPT -t nat -A PREROUTING -i $OUTSIDE -p tcp --dport 22 -j DNAT --to 10.0.0.10
#$IPT -t nat -A PREROUTING -i $OUTSIDE -p tcp --dport 2300:2400 -j DNAT --to 10.0.0.10
#$IPT -t nat -A PREROUTING -i $OUTSIDE -p udp --dport 2300:2400 -j DNAT --to 10.0.0.10
#
# Examples of allowing inbound for the port forwarding examples above or for
# allowing access to services running on the firewall
#
#
# If you want to be able to connect via SSH from the Internet
# uncomment the next line.
#
$IPT -A INPUT -i $OUTSIDE -d 0/0 -p tcp --dport 22 -j ACCEPT
#
#$IPT -A INPUT -i $OUTSIDE -d 0/0 -p tcp --dport 80 -j ACCEPT
#$IPT -A INPUT -i $OUTSIDE -d 0/0 -p tcp --dport 2300:2400 -j ACCEPT
#$IPT -A INPUT -i $OUTSIDE -d 0/0 -p udp --dport 2300:2400 -j ACCEPT
#
# The loopback interface is inheritly trustworthy. Don't disable it or
# a number of things on the firewall will break.
#
$IPT -A INPUT -i lo -j ACCEPT
#
# Uncomment the following  if the inside machines are trustworthy and
# there are services on the firewall, like DNS, web, etc., that they need to
# access. And remember to change the  IP to be that of the INSIDE interface
# of the firewall.
#
#$IPT -A INPUT -i $INSIDE -d $INSIDE_IP -j ACCEPT
#
# If you are running a DHCP server on the firewall uncomment the next line
#
#$IPT -A INPUT -i $INSIDE -d 255.255.255.255 -j ACCEPT
#
# Allow packets that are part of an established connection to pass
# through the firewall. This is required for normal Internet activity
# by inside clients.
#
$IPT -A INPUT -m state --state RELATED,ESTABLISHED -j ACCEPT
#
# Anything that hasn't already matched gets logged and then dropped.
#
$IPT -A INPUT -j firewalled