VPC Lambda internet access failure

Do you also have private and public subnet(s)? If your original VPC had only single layer (ie. public) subnet(s), then adding a NAT gateway and changing the default route from Internet gateway to NAT won't work because now NAT gateway don't have a route to internet any longer. Solution is to have public subnet (with a route to igw) and place NAT gw there, and private subnet with a route to NAT GW. Then you can place lambda functions into private subnets.

Here is an example how to create VPC with public and private subnets using VPC Wizard

https://aws-core-services.ws.kabits.com/two-tier-application-linux/vpc/create-vpc/

Your Lambda functions must be attached to a private subnet. Currently you have it attached to a public subnet, the same subnet you deployed the NAT Gateway. You set the route table for that subnet that all Internet traffic should go to the NAT Gateway. However, because the NAT Gateway itself uses the same route table, all it's traffic routes to itself.

Create some private subnets, attach the function to those subnets, set the route table for the public subnets to route to the internet gateway and the route table for the private subnets to route to the NAT gateway.