In the weird category. Make sure there is no ICMP filtering on either end. I don't know why so many IT "pros" think that firewalling ICMP is a good idea, especially when they can't tell me why they think it is a good idea. ICMP delivers a lot of important control messages (not just pings and traceroutes, but those are important too when things are not working correctly).
But yeah, this isn't an easy thing to trouble shoot. If I had time, and my hands on the gear to actually try things, then maybe we'd get somewhere...then again, maybe not.
