No service on jailbroken phone.

Iphone 4, ATT Locked.
Jailbroken using whatever latest version of redSnow was about a week ago.
I have a genuine Geveysim ultra.
ios 5.0.1, baseband 4.10.01

Wife hands me non-jailbroken phone, IOS 4.3.5.

I plug in gevey, follow instructions, get success first time.
It never works again. Always get "no service"

Upgraded to 5.0.1, preserving baseband with redsnow
Tried again with gevey ultra (yes, it is genuine, I checked for the dot), I never - and I mean never, get a signal.
Phone works wonderfully as an ipod touch.
She'd really like it to work on the O2 network here in UK.

Did O2 block me somehow? Did the jailbreak not properly activate the phone? After the itunes upgrade, I got scared because I couldn't get past activation screen. Couldn't do anything with the phone. Then the jailbreak got me past that.

The same O2 sim works fine in another cheap phone.

I'm at wits end. Any suggestions?
Network reset? New sim?

 

Tried that already. If you can't get signal, it (furiousmod) doesn't work either. I had to install from alternate site as recommended one constantly had bad url and other errors in middle of install.

I had high hopes for it, but alas, no dice.

 

Hard reboot doesn't help. If I do the manual 112 method, it pops up with a gevey screen that days "you have failed" then it asks me to reboot and try again. It also directs me to hevey website which is no help at all.

Pretty sure it has to do with no signal. If I go to the carriers and force select o2, it says that that carrier is no longer available.