Hey, I cannot get Edge either....
On 3G I can find my Carrier some times I even get 1 bar but no carrier shows up.. My phone is locked to o2 and I don't want to unlock.. I got my self a paygo sim on the day I got the phone it worked fine.. I got home updated and F*CK no service or searching tryed a lot of things nothing helps but I think I can't get service because 05.11.07 baseband locks the phone to o2 iPhone or contract sims, I'm going to try using contract sim see if it works... If not I'm going to o2 store and hopefully get it sorted.

Update: tried o2 contract sim from samsung g600 didn't work, going to o2 next week... But any info is welcome, by the way is
iPhone 3G
Baseband 05.11.07
Bootloader 5.09
unlockable?