Both on WiFi and mobile data, DNS resolutions fail instantaneously. I can load sites by IP address in Firefox, and I can connect to other machines using SSH by IP address, but anything that requires a hostname fails.
nslookup claims to using 0.0.0.0 as its name server. When I specify the server to use, such as 18.104.22.168, nslookup always fails:
nslookup: can't resolve 'startpage.com'
Sometimes after rebooting DNS works for a few seconds.
This is a rooted Samsung Galaxy SIII running Cyanogenmod 11 nightly build, Android version 4.4.4. The problem was the same on SlimKat.