This has cost me some hours of finally tracking it down, but I would like to know if someone can please shed light on this issue?
Android 6 and 7 do not accept DNS servers with IPv6 ULA addresses. Using some diagnosis apps, I can see that Android does in fact learn the DNS server addresses from router advertisements. But after some seconds, Android deletes them. But it keeps any SLAACed ULAs. Unfortunately, without DNS, these devices are pretty much useless in IPv6 networks with ULAs. (But see note below.)
In contrast, when using GUAs for the DNS server address, Android 6 happily learns and uses them.
Any reason why Android dislikes DNS servers with ULAs and only accepts "real" global addresses? Seems to take the meaning of "globalization" to a new level... ;)
Update 2: Android 7 in general does not accept ULAs, but instead considers such a network as not working and won't connect to it (tested with an Ethernet-wired Samsung Tab S7 running Android 7.0). Update: Android 6.x actually can accept DNS server ULAs, but I'm seeing this only when the network interface not only has an ULA, but also a GUA assigned. No GUA, then DNS server ULA get rejected. Now that is strange. I've updated the title to reflect this finding.