existem diferentes versões de traceroute - algumas dependem de icmp echos, outras de udp. se por algum motivo o seu firewall / operador bloquear esse tipo de tráfego - você está sem sorte.
tente mtr ou tcptraceroute .
também - não espere que todos os nós finais respondam às suas solicitações ou todos os roteadores no núcleo se incomodarão em enviar de volta o tempo icmp 'excedido em trânsito'.