http://shop.o2.co.uk/update/unlockmyiphone.html
Enough said. Unlocked within 14 days.
[update: mine is done now. I got an SMS from O2, then I had to put a non-O2 sim in and connect it to iTunes. After a couple of minutes, it got a new Carrier settings, and it works. Yay!]
