It's been a very long time since I've diagnosed something like this, but I've had problems in the past when the MTU is smaller than the default and ICMP is blocked (interfering with path MTU discovery). Often IPSec or some other tunneling was involved. The initial packets got through but as soon as a full packet was sent it was dropped.

EDIT - I've now scrolled down in HN and saw that this was ruled out.