Change your DNS servers in Android.
You can change the same thing on your rooted Android Device.

With root privileges and a terminal app or (adb shell):
root@:/ # ndc resolver flushif -- flushes old DNS servers
root@:/ # ndc resolver flushdefaultif -- flush resolver
root@:/ # ndc resolver setifdns <iface> <domains> <dns1> <dns2> ... -- Add the new servers
root@:/ # ndc resolver setdefaultif -- Set as the default device