You could also use tcpdump to record packet captures on both machines (to see if the ICMP packets are sent properly or arrive properly). This can confirm that the problem is somewhere in the middle, rather than a firewall rule or something on one host or the other.