Just had an issue where traceroute w.x.y.z failed however ping w.x.y.z worked fine....

The fix:

traceroute -I w.x.y.z
or
traceroute -T w.x.y.z


Where w.x.y.z is the IP address of the remote host e.g. 10.22.34.8

By default the Linux traceroute was using UDP which must have been getting blocked by firewalling somewhere.

Changing to -I (Use ICMP ECHO for probes) or -T (Use TCP SYN for probes) seems to fix the problem.