А ты уверен, что там именно настоящий полноценный нат? Я вот сомневаюсь. Мне всегда казалось, что оно использует сетевой стек компа более-менее напрямую, а ICMP в такие костыли плохо вписывается, если вообще. И как ты пингуешь, через adb shell? Я бы посмотрел, для начала, сниффером, что там отправляется и что и куда приходит.