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):

1. Enable developer mode (Go to Settings -> About phone, and click on the build number until the developer mode is enabled).
2. Enable USB debugging under Settings -> Developer options
3. Connect the device with a USB cable to a computer with the Android SDK platform tools installed
4. Start an adb shell: adb shell
5. In the adb shell, run this command: settings put global tether_dun_required 0

For rooted phones, this alternate procedure can be done without connecting the device to a computer:

1. Root the phone
2. Install a SQLite editor such as SQLite Debugger
3. Using the SQLite editor, navigate to the file /data/data/com.android.providers.settings/databases/settings.db (this is the part that requires root)
4. Enter the database global
5. Change the value of field tether_dun_required to 0.

Tether away!