It is either mail isn't listening for connections originated from other than localhost, or believe it or not there is a firewall running.
Here is the rule to open it up
Code:
$IPTABLES -A INPUT -i $EXTIF -m state --state NEW,ESTABLISHED,RELATED -p tcp -s $UNIVERSE -d $EXTIP --dport 25 -j ACCEPT
Where is $IPTABLES=/path/to/iptables, $EXTIF=external interface such as eth0 and $UNIVERSE=0.0.0.0/0, and $EXTIP=your IP