How to you set up private nameservers when using AWS Route53 and EC2

In order to do this, you will need an NS record on the zone hosted at DnsMadeEasy for each subdomain. This action is called "delegating a subdomain" to an external DNS server. Here's the DNS Made Easy guide for that.

For instance, you would need an NS record in the parent zone for: tenant1.example.com, which points to the four namserver addresses assigned to you when you create a tenant1.example.com hosted zone in Amazon Route 53.

Create your hosted subdomains in Amazon Route 53:

Then make sure DNS Made Easy has an entry like this for each subdomain:

The original form of this answer was a train wreck. Abandon all hope all ye who view edit history. Here's the re-done and more-right answer.

If I understand you correctly, you are using Route 53, but don't want to give your clients the ugly Amazon URLs. You want your clients to point their domains' NS records to your DNS servers that will be given more-attractive-than-Route53-style names. You will manage DNS records in R53, but you will then need to replicate the zones down to your servers so that they are in sync. Your comment confirmed that suspicion:

I need to prove that this concept is not the correct one, because my boss thinks that passing for clients the ugly DNS is bad somehow

First, do not CNAME your name servers to Route53 and then have your clients point their NS records to your CNAMEs. As you have found out, that often isn't even allowed in certain applications.

Your best bet would have been to simply perform a zone transfer from Amazon to your BIND servers. Except, at the time of this post and in the words of an Amazon employee in this thread:

AXFR/IXFR is a feature we will consider adding in the future, but have no firm plans for at this time.

If you require zone transfers for Route 53, the options that I'm aware of are easyRoute53, and http://romana.now.ie/route53d/ (IXFR only).

At the time of this post, the only major public third party integration with Route53 is easyDNS's easyRoute53 which will push easyDNS zones to Route53 as secondaries, but that's not what you're looking to do. That solution would mean easyDNS is your primary nameservers but you want to use your own metal.

So now what? It appears that you will need to write some custom middleware that queries Amazon's name servers for individual records and updates your BIND servers' records. Except that makes no sense for about nine different reasons, but ultimately the biggest problem is that you've scoped your point of failure down to your own servers anyway, so why bother with Amazon at all unless you think Jeff Bezos needs more money.

If you must have pretty name servers either just use your own metal and manage your own DNS service stack or move to a different DNS service that offers you the ability to whitelabel DNS management and use your own vanity name servers. I won't list any services that would do that since they'll go out of date. At this point there is no advantage to using Route53 for what you want to do and there is only disadvantages and downtime in trying to make it work.