O problema acabou sendo o firewall (não o Ubuntu ufw, mas o firewall fora do meu servidor fornecido pelo nosso departamento de TI) não permitindo a saída de pacotes ICMP.
Uma vez que isso foi ativado, a descoberta do caminho da MTU (ou o que quer que esteja acontecendo) começou a funcionar e tudo está bem.