Eu não sou um especialista em iptables e faz muito tempo desde que eu tive que me meter no iptables, ... mas eu acho que você precisa adicionar uma regra para aceitar o ping echo-request:
-A INPUT -p icmp -m icmp --icmp-type echo-request -j ACCEPT
A regra que você tem para o echo-reply permite que seu servidor Ubuntu faça o ping em outro servidor, mas não permitirá que o outro servidor faça ping no seu servidor Ubuntu. Deixe-me saber se isso funciona, por favor.
Estranho, de fato, que funcionou antes. Você alterou a política padrão na entrada por acaso?