O problema era que eu precisava ter um NAT na sub-rede na qual a função Lambda está sendo executada - um Gateway da Internet não é suficiente!
Suponho que isso ocorra porque o Lambda é executado apenas em particular e o Gateway da Internet, que permite tráfego de duas vias, não permitiria rotas de / para o Lambda.
Adicionar o Lambda a uma sub-rede privada com um NAT anexado resolveu este problema.