Установите tcpdump на маршрутизаторе, запустите его так:
tcpdump -i tun0 -n -s0 -w /tmp/dump.pcap port 53
Где tun0 — адрес VPN-интерфейса, после чего откройте Google Play и воспроизведите проблему. Как только получите ошибку, остановите захват tcpdump комбинацией ctrl+c, скачайте /tmp/dump.pcap с маршрутизатора и загрузите сюда.
Лучше всего за 10 минут до начала процедуры не открывать Google Play на телефоне, а делать это только после запуска tcpdump.