Which kernel version are you using. I think 2.0 would not masquerade ICMP.
With 2.2 you have to have ICMP masquerading enabled in the kernel config.
A clue is to look in your linux source tree if you built your own kernel
and check in .config for the value of:
CONFIG_IP_MASQUERADE_ICMP
and make sure it is set to y or m
If it is set to m, there should be a module in:
/lib/modules/`uname -r`/ipv4 something along the lines of ip_masq_icmp.o
If it is there try loading it with
insmod ip_masq_icmp
then see if ping works from your private net to the internet.