Hey tech.gsr, this is sort of a cop-out...
but rather than debugging this step by step, here's another thought.
I'd recommend, particularly for someone fairly new to linux, installing a gui firewall package (if you have a desktop linux setup, such as gnome or kde). In that case, I can guarantee you will be able to not only get the boxes to ping each other, but you will be able to enable and disable pings at the check of a box. My preference is firestarter, although it has not had any active development for awhile, it works fine for me. Here is a link to install it on fedora:
Install it (on both linux boxes), and there is a checkbox for allowing/disallowing pings in the menus. You can also open up any ports you want, etc. Also, if you don't like using the package, you can use it to produce your iptables rules, and then you can set up a startup script for iptables, and not need the gui frontend. That way, you can see what is actually needed to enable pings.
Will a gui firewall frontend to iptables work for you? This is what firestarter is. It also has some nice features -- you can monitor all active connections to the box, etc.
If you are purposely avoiding a gnome/kde desktop, or a gui firewall interface, then back to the drawing board.