Qual versão do Android você está usando?
Ser capaz de fazer ping no seu gateway apenas diz que ele pode falar com o seu telefone - o que implica que o problema está no encaminhamento dos pacotes pelo telefone. A referência a www.google.com pode ser uma entrada de DNS em cache, não ativa. Atualmente estou tentando algo parecido com bluetooth e vendo relatos de tethering do JellyBean sendo aleijado.