"Could not activate cellular data network" three days after successful unlock
iPhone 3GS, 3.0:
Jailbroken with purplera1n, then unlocked with ultrasn0w.
Running on legit O2 SIM card.
It used to work absolutely fine with any problems (also with my other SIM card), but out of the blue today, whenever I want to connect to the internet it breaks off with "Could not activate cellular data network".
Tried to reset network settings, switching on and off 3G/flight mode, all without any result.
Any ideas what I could try before doing a complete restore?
Also, and hints what I should do before doing the jailbreak/unlock again? I just used it plain vanilla, with the O2 Sim card in there as the unlock did its thing...