Вероятнее всего, с различием в адресах, который отдает DNS для России, и с адресами, которые выдаются с вашего сервера.
Запустите что-то вроде tcpdump -n port 53 на сервере, и смотрите, какие домены запрашивает телефон, в какие IP-адреса они резолвятся, и доступны ли эти адреса из России.
Как только определите домены, добавьте их резолвинг через DNS Яндекса, например, это должно исправить проблему.