It pops up a message telling me this which means I have to tap 'OK'
This is seriously annoying, does anyone know why this happens and what terrible event it is supposed to help me avoid?
This is annoying but you can't turn it off unfortunately. If the iPhone detects a momentary loss of connection to the cell tower and it believes the user is interacting with the phone then it will pop this message up. It's intention is to let you know that you don't have a signal and therefore won't be able to send your SMS, email etc. however more often than not it's a sub-second blip in the signal rather than a total loss. If you watch closely you'll sometimes see the signal bars disappear and reappear as the signal is reacquired.
You could try going to Settings > General > Reset > Reset Network Settings to see if somehow you've altered some network setting which is affecting your reception but you'll lose wifi passwords etc I think if you do that.
I had the same problem on a new iPad (2012 model) with T-Mobile in the UK.
Solution was easy once I found it (credit: this answer) - just go into Settings > Carrier, and turn off Automatic (i.e. selection of carrier). When your carrier is listed below (may take a minute or two), just select it.
This completely fixed the problem, which wasn't fixed by going into airplane mode, rebooting, or tweaking the APN settings.
Update: unfortunately this turned out not to be a complete fix after some time using this, though it did improve matters. Using a Vodafone SIM worked fine, so I suspect the problem is with T-Mobile UK.