The Microsoft traceroute command uses ICMP and the Cisco/UNIX traceroute command uses UDP (icmp unreachable will be returned though).
Here is a good link explaining: http://www.cisco.com/warp/public/105/traceroute.shtml
Here is a good link on how to allow it through your firewall:
http://www.cisco.com/en/US/products/hw/vpndevc/ps2030/products_tech_note09186a00800e9312.shtml
I don't think one method is necessarily better than another, just different implementaions. You have to know both for your firewalling.
Although if I had to argue one against the other I would say UDP is better:
1) ICMP will be filtered more often than UDP by acls and firewalls and rate-limiting
2) due to the security risks ICMP pose.
Hope it helps.
Steve