I managed to get a great deal with Three UK with unlimited data for £12.90 and added 1GB of personal wifi hotspot allowance for an additional £5.00 a month.

The hotspot allowance is great as it means I only need one SIM for all my devices when I am out and about.

It all worked fine until I upgraded my phone (a Sony Xperia Z2) to Android Lollipop (v5.0.2) at which point my hotspot stopped working. Devices could still connect to the phone, but showed DNS related errors when they tried to access the internet.

Contacting Three and Sony customer support did not solve the problem but eventually I found the solution at http://forum.xda-developers.com/z3/general/lollipop-tethering-t3058923 (hooray for XDA developers).

I reproduce the solution here:

1. enable developer mode (Settings->About Phone, click several times on the build number until you see a message which says developer mode is activated)
2. enable USB debugging (Settings->Developer Options->USB debugging)
3. install the Android SDK on your computer to get the ADB executable and add it to your PATH
4. connect the phone to the computer via USB
5. open a command line/shell
6. use the command line/shell to start an adb shell (adb shell)
7. execute the following command in the shell:
   settings put global tether_dun_required 0

No root access is required and no reboot was required; the next time I started up the portable hotspot devices could access it with no problems at all.