I'm still working on the problem, it looks like it may be a firewall issue. The firewall is blocking ICMP type 3 code 4 packets (Dest Unreachable).
Via this webpage,
http://www.usenix.org/events/lisa02/tech/full_papers/vanderberg/vanderberg_html/
and other web into, I see that this particular ICMP packet hold MTU info, and should be allowed to pass through the firewall, currently, all ICMP packets are dropped by default. Unfortantely, I don't believe our current firewall allows a configuration that would allow ICMP 3/4 to pass. Looks like it's time to upgrade to a PIX!!