Aha! I've cracked it. The FRITZ!Box is a pain to configure... For the benefit of others, I had specified the DNS Server under Internet -> Account Information -> DNS Server but that's not correct. It's necessary to go into Home Network -> Home Network Overview -> Network Settings -> IP4/6 Addresses then enter the IP address of the Pi Hole device under "Local DNS server".
Thanks for your fast help though, Mcat12! It helped me at least narrow down the problem.