Windowsのtracert と Linuxのtracerouteに違いがありました。

tracert:Windows ⇒ Dstに対してICMPパケットを送信
traceroute:Linux ⇒ Dstに対してUDPパケットを送信

Linux に対して、Pingは通るけどtracerouteを返さない場合は、ICMPは許可されているがudpポートが開いてない場合です。
Traceroute のUDPポートは以下になります。
tracerouteのUDPポートだけを開けたい場合は、33434 to 33534 を明けてあげれば良い。

UDP src port 0-65535, dst port: 33434 - 33534

Linuxの場合、-I オプションを付ければ、ICMPを利用します。

$ traceroute -I DST

https://en.wikipedia.org/wiki/Traceroute