You can use TCP/UDP/GRE for your traceroute packets with the -P switch:

traceroute -P udp <hostname>

This is super useful if you're probing a network that's hostile to ICMP packets - it's a lot more reliable than ICMP in many scenarios, from my experience.