As Daniel Pocock points out, Google made a change in Android 4.4 which allows operators to know when users are using tethering and conveniently block tethered devices from accessing internet. This can be fixed permanently using the following procedure (UPDATE: no root required): Enable developer mode (Go to Settings -> About phone, and click on the build number until the developer mode is enabled)