@DaveK , From your description, it seems the network access via Microsoft Tunnel Gateway is working well. But when we use FQDN it is failed. And google.com is also not accessible.
To clarify our issue, please firstly check if the issue is only with one Android device. If it is only with one, it seems the issue is on device side. we can try to clear the cache on the device and restart the device to see if it can work.
If the issue is not only on this affected device, based on my experience, we can check if we get the correct DNS server we want. On DNS server, check if the DNS request has been sent to the DNS server and if it get any error when resolve the FQDN. Also we can view Microsoft Tunnel logs to see if there's any more finding.
https://learn.microsoft.com/en-us/mem/intune/protect/microsoft-tunnel-monitor#view-microsoft-tunnel-logs
If we want the help to look into the logs, to protect the sensitive information in your environment, we suggest to open case to troubleshoot on it. Here is a link with the steps to open case for your reference:
https://learn.microsoft.com/en-us/mem/get-support
Thanks for your understanding.
If the answer is helpful, please click "Accept Answer" and kindly upvote it. If you have extra questions about this answer, please click "Comment".
Note: Please follow the steps in our documentation to enable e-mail notifications if you want to receive the related email notification for this thread.