Les seuls problèmes de traceroute impossibles que j'ai et que j'ai eu, c'est et c'était à cause de mon pare-feu, côté ordinateur...
Quand je n'ai pas besoin de faire un traceroute, je paramètre mon pare-feu pour que cela ne soit pas possible. En réalité, c'est un effet collatéral d'un paramètre qui ne devrait uniquement interdire le ping vers ton ordinateur. Mais pour le coup, pas de traceroute en sa provenance. Il faut donc autoriser le ping sur le pare-feu de son ordinateur pour avoir un traceroute fonctionnel.
C'est peut être logique après tout, mais bon, pas évident de prime abord. Ou un bug de certains pare-feu...