OK. This problem is solved and it created another confusion. (There were no firewall rules btw.)
This was great tut. So here's my network layout
Internet <-- EVDO Internet Data Card <-- Host (NAT) <-- Client 1
^ ^----- Client 2
There's no client 2 actually but it would work now. Config's done.
Now new confusion is...
route add -net 192.168.1.0 netmask 255.255.255.0 gw 126.96.36.199 dev eth0
If I add same command (with needed modifications like ppp0 as dev and different gw) in my host machine, things don't work. And if I remove this particular custom route, things work. Any idea why????