After a few more hours of troubleshooting and reading I found there is a feature in DNSMasq that protects you from a DNS Rebind attack. Unfortunately, the way Netflix works it uses something that looks just like that, so your DNS queries don't work and you get no video.
With most setups you could change the DNS server of your Apple TV (and iPhones, because this happens on them also) to the google address (188.8.131.52). Of you can look at your router to see what your ISPs DNS server is and use that.
If you are using DD-WRT, you can upgrade (or look, you might already have this feature if you upgraded in the last 2 months) to a version that has "No DNS Rebind" on the services page in the DNSMasq section. This turns off that security feature. Below is a picture with it turned off. Be sure to reboot your router after you make this change.
If you are using DNSMasq on something else, look into a way to turn off DNS Rebind protection. There are several commands out there for Linux based systems, but I don't have the time to go check them. You can start at this link that has some of the commands: