Yeah, you are right it can't be a DNS issue alone. If it was, I guess setting the phone to use OpenDNS would've resolved it. It must be a weird combination of things.
But I'm curious; is anyone else able to access websites in the browser by using IPs, like I am (try 74.125.45.100 and see if you get to Google)?