We've seen this happen on devices connected to O2 before, but I've never figured out what is causing the issue. I have a theory that it's caused by devices that were previously connected to a BES server at a large company, looking for a system called the MVS, or Mobile Voice Service and being unable to find it. This may or may not be the case, so here are some general tricks you can try.
It would be a good idea to top up your service with O2 first, just to see if that can be a simple way to resolve your issue. If, after this, your still having the issue, I'd suggest checking your device for an IT policy.
You can easily check for an IT Policy via going to the homescreen and typing "it policy", which should bring up universal search and show you the spanner icon for options, navigate to it and the option should be "Security Status Information. Click that and make sure it says "*No Services*".
If you find that your device shows entries in that screen, you'll have to do a hard reset in order to remove that IT policy. Some prefer to use the command line to remove IT policies, as was shown on the BlackBerry Help Blog, or some use an application like BBSAK to remove it. Both of which are doing the same thing, it just comes down to personal preference, do remember that if you decide to follow this path, all data on the device will be removed and unrecoverable, so be sure to backup before hand.
If your still having an issue, It would probably be best to get in touch with O2, either via phone or via popping into a local O2 shop and explaining the issue your having.