How about if you turn of your iptables/ipchains for a minutes and try do traceroute again..if that one works you need to reconfigure your iptables/ipchains rules.