This sounds like a problem where your router at hop 1 is blocking ICMP TTL Expired packets.

We cover this topic here:

http://www.nessoft.com/kb/29

Often, updating the firmware bios can solve this, or possibly changing some packet settings in the firewall to allow ICMP through.