Just thought I'd add my experience.
I'm still under commitment on my iPhone 3G. I have since 'upgraded' as O2 suggested, by buying a PAYG iPhone 3GS from O2 and putting my iPhone contract SIM into it.
My iPhone 3GS was successfully unlocked. I'm happily on Vodafone paying £20/mo for 600 mins, unlimited texts, unlimited data and, most importantly, coverage and a network that works
My iPhone contract SIM is now back in the iPhone 3G, for which I have now also requested an unlock. Hopefully that will be granted, too. Then I can cancel the contract in January and put the whole O2 'experience' behind me.
Don't get me wrong, they're far from the 'worst' network in the UK, and I appreciate coverage and network performance is incredibly location sensitive. For me, though, being on Vodafone is like having a whole new iPhone.