Windows tracert sends ICMP requests, while Unix/Linux traceroute sends UDP packets bound for UDP high ports. Use the tracert command from Gaia/Linux and it will work, you must be blocking UDP high ports somewhere in the path but not ICMP echo requests.
Edit: Windows tracert expects to get ICMP echo replies as responses, while Unix traceroute expects to receive Destination/Port unreachable responses. So those latter types of responses could be getting blocked.
Attend my Gateway Performance Optimization R81.20 course
CET (Europe) Timezone Course Scheduled for July 1-2