What is DNS rebind protection?
If your router has an option called DNS rebind protection enabled, you may run into issues when trying to use Pi-hole as your DNS server. The reasons for this are quite technical, but to summarize what this option does in one sentence:
DNS rebind protection does not allow DNS queries to be answered with a local IP address.
Why does this interfere with Pi-hole?
DNS rebind is meant to be a countermeasure to an attack on your network. So in many cases, it's actually a good thing by preventing your DNS queries from being compromised by not allowing DNS queries to be handled by a server with a non-routable (private) IP address. But in the case of Pi-hole, it's set up on your private network (but not in every case) so you are in control of your own private DNS server.
Knowing that, DNS rebind protection is a direct contradiction to how Pi-hole functions to block ads for your entire network. Pi-hole is a local (a.k.a. private) DNS server as opposed to using a public one like Google's.
With rebind protection enabled, your router thinks Pi-hole is something malicious since it is acting as a DNS server within the private IP address space. You may see something like this in your log files:
Sun Apr 30 15:30:08 2017 daemon.warn dnsmasq[3408]: possible DNS-rebind attack detected: pi.hole
But notice how is says possible attack detected. Private DNS servers are not uncommon and perfectly legitimate, which is also why you can enable and disable rebind protection.
Specific problems and examples of DNS rebind protection interfering with Pi-hole's operation
OpenWRT
You can disable it in /etc/config/dhcp by setting this to 0:
option rebind_protection 0
DD-WRT
DD-WRT has a similar option you can set for specific domains:
rebind-domain-ok=/plex.direct/
rebind-domain-ok=/pi.hole/
Fritz!Box
Several users have run into issues with these model routers as it's often enabled by default. In addition, it has been reported that the option for DNS rebind isn't even available until a certain version of firmware is installed.
I'm still having trouble resolving domains after disabling rebind protection
You are likely running into caching issues. Flush your cache and try again.
What else can I do if nothing else works?
Pi-hole now ships with a built in DHCP server. You can disable DHCP on your router and use Pi-hole to handle DHCP (and DNS).
This FAQ attempts to condense and clarifies the data dump found here as well as other forums and posts across pi-hole.net.