I have found something promising that can get Debian to work properly.
Add the following to the bottom of Debian's /etc/resolv.conf
options single-request
Ping and traceroute etc started working.
Obviously you shouldn't have to modify clients to get OpenWRT to work properly. Would be interested in what caused this and whether it can be fixed in OpenWRT.
EDIT:
Details of this resolv.conf option from the resolv.conf manual:
single-request (since glibc 2.10)
Sets RES_SNGLKUP in _res.options. By default, glibc
performs IPv4 and IPv6 lookups in parallel since
glibc 2.9. Some appliance DNS servers cannot handle
these queries properly and make the requests time
out. This option disables the behavior and makes
glibc perform the IPv6 and IPv4 requests
sequentially (at the cost of some slowdown of the
resolving process).
EDIT2:
The following option works instead in Debian's resolv.conf
options single-request-reopen
Details from manual:
single-request-reopen (since glibc 2.9)
Sets RES_SNGLKUPREOP in _res.options. The resolver
uses the same socket for the A and AAAA requests.
Some hardware mistakenly sends back only one reply.
When that happens the client system will sit and
wait for the second reply. Turning this option on
changes this behavior so that if two requests from
the same port are not handled correctly it will
close the socket and open a new one before sending
the second request.