AWS Cloudformation: Create Route to an Instance - CF can't find instance ID

I'm unable to create a route that points to the interface of an EC2 instance (NAT box in my public subnet). I used a DependsOn attribute in the Route resource, and I can see in the CF log that the instance is created before CF tries to create the Route. However, it errors out saying "The gateway ID 'i-xxxxxxxx' does not exist".

"RoutePrivate1": {
            "DependsOn": "EC2InstanceNAT",
            "Properties": {
                "DestinationCidrBlock": "0.0.0.0/0",
                "GatewayId": {
                    "Ref": "EC2InstanceNAT"
                },
                "RouteTableId": {
                    "Ref": "RouteTablePrivateSubnets"
                }
            },
            "Type": "AWS::EC2::Route"
        },

I can manually go into the route table, and add that very gateway id without issue. Could I be hitting a race condition? Or am I doing something wrong?

Thanks for any help!

_KJH