I know you have got to the bottom of your issue, but just wanted to added this.
I actually get this on Three (4G suddenly disappears) when the power goes out locally. I couldn't get 4G back until I call them up and get a Network Refresh done on the connection. With the amount of lightening recently, this has been happening a lot in my area.
Last time it happened I got a little angry and my call was escalated to the higher level tech support (the low level ones repeatedly tell you to turn it off, dance around in an anti-clockwise direction, go outside, ring the doorbell and then switch it on again). This higher level tech said that the only way for me to resolve this was to register on the 3G service first, use a bit of data and then search for and connect to 4G. This did seem to work, but looking for a more technical reason as to what is happening!!