I actually hit this problem, and I fixed it by modifying the routing table associated with my VPC to route ::/0 to an Egress Only Internet Gateway. (Just _adding_ the EIGW to a VPC is not sufficient, because routes aren't configured automatically.)

So I'm guessing that was the issue here.