Iphone 3gs on o2 network, how can i unlock it ?

[bestinn]

Sir,
I have iphone 3gs with new bootroom and latest software version which is 4.1. I am from Pakistan and i purchased it from market. Previously it was on 4.01 and it was unlocked through ultrasn0w. But recently i update it. Because i was thinking that it is factory unlocked... now my fone is locked and i just jealbrak it.
Now i want to ask all of you and specially for those people which are living in uk and using o2 network, can they tell me that how can i do unlock it from o2 uk. Because it come from uk and i can activate it usinh o2 sim, but can't use local carrier sim.
I here that o2 carrier can unlock it with a some fee like 25-35£. If it is yes then how can i do it, can anybody help me in this regards ?
I will be very appriciate.
Thanks.
Sorry for my broken english.