The system works by accessing DNS and check if the resulting IP is owned by google.com or some network-internal redirection/replacement by a login page.
Now, the IP 126.96.36.199 is owned by Google, so the DNS lookup obviously worked perfectly but for some reason the phone gets an unexpected answer from that server. Which makes me guess to one of the 2 following options:
a) one of the computers in your network is infected and Google keeps showing the "Prove you're human" captcha window on requests.
b) your provider is replacing failed DNS lookups with it's own "helper" page which for some reason is making Android trip. If possible, change the DNS servers in your router to either OpenDNS or Google DNS.