Demorou uma atualização (não recomendado, fazer uma nova instalação) para descobrir que era iptables depois de tudo. Fazer iptables -F não foi suficiente, levou service iptables stop para realmente eliminar essa regra obsoleta.
Estou tendo um problema estranho com um servidor RHEL 5. Eu mudei seu endereço IP, estamos migrando para um novo pool de endereços, e algo está bloqueando todo o tráfego de saída, mas eu posso fazer o SSH nessa interface (eth0). Todo o tráfego funciona corretamente em nossa rede privada (eth1). Eu corri o iptables por isso não deveria estar no caminho. Minha tabela de roteamento se parece com outro servidor RHEL 5 que fez o switch sem problemas. Eu reiniciei e também não tive alegria. Onde mais poderia estar escondido um endereço IP antigo latente que está causando esse problema, porque quando eu alterno de volta para o endereço antigo, ele funciona muito bem.
EDIT: Como solicitado aqui é a tabela de roteamento e saída de 'arp -n'
# route
Kernel IP routing table
Destination Gateway Genmask Flags Metric Ref Use Iface
*****.56.0 * 255.255.255.0 U 0 0 0 eth0
10.0.0.0 * 255.255.255.0 U 0 0 0 eth1
default gateway.***** 0.0.0.0 UG 0 0 0 eth0
# arp -n
Address HWtype HWaddress Flags Mask Iface
******.56.254 ether 00:A0:D1:E4:58:0D C eth0
10.0.0.203 ether 00:40:05:A0:21:93 C eth1
10.0.0.128 ether 00:21:5A:4C:1C:40 C eth1
10.0.0.129 ether 00:21:5A:47:36:80 C eth1
10.0.0.1 ether 00:0A:CD:20:64:28 C eth1
10.0.0.130 ether 00:22:64:0D:A5:46 C eth1
10.0.0.125 ether 00:22:64:0D:B5:A0 C eth1
10.0.0.127 ether 00:22:64:0B:D1:B0 C eth1
10.0.0.126 ether 00:21:5A:4C:4B:14 C eth1
10.0.0.124 ether 00:22:64:06:F8:AE C eth1
Como eu mencionei, a rede privada funciona bem e essas máquinas podem ser vistas na tabela arp.
O seu Gateway está configurado corretamente para o novo IP? Você está na mesma sub-rede que o IP anterior? O que você quer dizer com tráfego de saída? Você quer dizer alguma coisa além da mudança, ou você quer dizer que você não pode pingar um computador na mesma sub-rede? Se for o primeiro, verifique as configurações do seu Gateway.
Você pode acessar o gateway da caixa em questão? Eu suponho que você pode pingar 127.0.0.1 e o endereço IP configurado. Se você tiver acesso ao switch, você deve poder fazer o mac do nic e confirmar o vlan em questão (supondo que você possa acessar o switch da caixa).
Você pode confirmar que a máscara de rede está correta? Eu também gostaria de chamar sua atenção para quaisquer configurações relacionadas a selinux e iptables, (mas parece que você já está cutucando lá).