Android Tethering DNS Problem
I ended up manually changing my DNS server to tether Internet from my mobile phone. My phone uses a local DNS server from my mobile carrier which I was able to trace using CompruebaIP.

Any other DNS server is blocked by my mobile carrier (Globe Telecom). I reckon that my phone's DNS service is not properly working. When tethering, the DNS provider should be my phone which serves as proxy when connecting to my mobile carrier's DNS servers. Thus, I had to set them manually on my laptop.

I am using Windows 8 and my phone is an Android Gingerbread 2.3. So basically, the problems are:


My mobile carrier is bad. They are blocking other DNS servers and are monopolizing DNS requests. This isn't good because their servers aren't that good.
My phone's DNS service appears to be broken. This means my laptop could not connect to the DNS service of my mobile phone which then forwards DNS requests to my mobile carrier's DNS service.


Fortunately, after two months of despair, I was able to resolve this. This is what I did:


Find out what the actual DNS servers are my mobile carrier is using through CompruebaIP.
Manually set my laptop's DNS servers to the one used by my mobile carrier.
Even better, I retained Google's Public DNS server 8.8.8.8 as my primary DNS server and used my mobile carrier's primary DNS server as my alternate DNS server.


So, now, I can use my mobile phone as my Internet provider for my laptop whenever I am not at home or at work without having to change anything every time I use it.