Ah, a resposta do mistério "Como compartilhar a rede no Fedora 4"

Descobri o que estava bloqueando o compartilhamento no Fedora dos klein: o tal do SELinux.

O SELinux - Security Enhanced Linux - nada mais é do que algumas regras de firewall e políticas de acesso a recursos do kernel/sistema.

Para compartilhar o Fedora em questão eu fiz um scriptzinho que segue:

#!/bin/bash
#
# script: Configura-conexao
# versao: 0.1
# Cliente: Familia Klein
#
# Script para configurar o compartilhamento internet no Fedora Core 4,
# usando o SELinux e as ferramentas do próprio projeto Fedora
#
# Modo de uso:
# Numa tela de terminal, executar como root:
# # chmod +x configura-conexao
# # ./configura-conexao
#
#
souroot=`whoami`
if [ "$souroot" != "root" ];
then
echo "Este script precisa ser executado como root."
exit 0
fi

# Ajustando o SELinux para Masquerade
system-config-securitylevel-tui -q --trust=eth1 --masq=eth1 --enabled
echo
echo "Mascaramento ajustado."

# Ajustando o IP_Forward no kernel
cp /etc/sysctl.conf /etc/sysctl.conf.old
sed -e 's/ip_forward = 0/ip_forward = 1/g' /etc/sysctl.conf.old > /etc/sysctl.conf
echo
echo "Controle de inicialização ajustado."

# Habilitando o Ip_forward
echo 1 > /proc/sys/net/ipv4/ip_forward
echo
echo "Compartilhamento de internet ajustado."