[ran-o-matic]

Something weird is definately going on. As I said, a DNS problem doesn't seem too likely, but then again, nothing else seems likely either. Heck, the OP is saying he had this problem with the stock ROM.

My NAT suggestion is based on an actual problem I have seen. In that case, the person configured a NATed router and did not use one of the address ranges reserved for private networks. Surprisingly, web browsing worked, but a custom apps we develpoed had problems. We corrected the private address range and the problem was solved.