I had this same issue. It turns out my phone was from Asia. Accessing the service menu does indeed enable it but only until you reboot your phone.
The only cure I found was to flash a UK stock rom. Very easy to do and now I have 4g everywhere I go (well almost)
Current Phones: HTC One, S3, SE Xperia X10i.
Current Tablet: Nexus 7