Thanks for your answer.

Yes I did all of that, as well as allowing the traffic coming from my NAT Instance as an inbound rule of the Security Group of the private instances (and the other way around), and no restriction on the outbound traffic.

I suspect that the NAT Gateway IP was "hard coded" in Databricks Control Plane (associated with my VPC reference) when it was provisioned by CloudFormation, but I don't know how it could be updated with the IP of my new NAT Instance (since this update should be made by Databricks).