Eu entendi! O problema estava no roteamento da VPN. A VPN não estava configurada no modo de comutação, portanto era impossível rotear pacotes que precisavam ser encaminhados pelo gateway. Eu uso tinc vpn, então adicionando um Mode = switch a tinc.conf no gateway e os clientes fizeram o truque!