AD allows for a lot of granularity with perms to various pieces of the tree. I am confident that it is not a "Allow DNS lookup" perm problem. It only looks to DNS for GC reference, not for the AD query. For the AD query, it looks to well.... AD.
_________________________
Give a man a fish and he will be back for more. Slap him with a fish and he will go away forever.