NextDNS not working on specific network on specific device

Hi,

On a specific WiFi network, I can't get NextDNS to work on my Android phone. When I have Private DNS turned on, being connected to the WiFi network, internet connection breaks with a notification saying "Private DNS can't be accessed". And truly, I can't ping dns.nextdns.io ‒ "unknown host".

ping.nextdns.io results:

anexia-bts                 5 ms
  zepto-vie                  8 ms
  exoscale-vie              11 ms
  anexia-prg                11 ms
  enahost-bts               12 ms
  anexia-bud                18 ms
  edis-bud                  19 ms
  zepto-zag                 20 ms
  anexia-vie                21 ms
  edis-zag                  23 ms
  anycast.dns1.nextdns.io   error  (anycast1)
  anycast.dns2.nextdns.io   error  (anycast2)
  dns1.nextdns.io           error  (ultralow1)
  dns2.nextdns.io           error  (ultralow2)

Strangely, NextDNS works perfectly fine on the same network from my Linux PC. So it's not the network? I don't know. Diag from my PC: https://nextdns.io/diag/ebd437d0-ae38-11ef-bfba-c5d9d021bd12

I'd be grateful for any pointers or additional diagnostic tools.