It's possible that the SIM card was provisioned improperly by the carrier or that there's a hardware problem with the SIM slot. I can't think of anything else.
If you still receiving this error w/ a brand new SIM Card then I would definately contact O2 to have them verify the ICCID (SIM Number) and validate that the device needs to be replaced.
__________________
BlackBerry 7100t on Legacy AT&T Wireless