I remember with the original iPhone you could upgrade to the 3G version in your contract and just sign up for another 18-months. This makes sense. Paying off the remainder of your contract to upgrade to the 3GS, doesn't.
That was because the first version was sold at a non-subsidised price. So the airtime contract didn't contribute to O2's cost recovery. The 3G version was subsidised by the 18 month airtime contract, so O2 would lose money if they let you cancel your contract prematurely without penalty.
I haven't yet been able to find out what they want to cancel my remaining contract time, as the O2 CS person I spoke to yesterday had been given no information and had no access to the O2 web pages I was looking at. She asked me to read off the tariffs to her! I suspect the cancellation fee will vary according to what contract you are on, what phone and contract you want to buy next, who you speak to, the phase of the moon, and other factors we can only guess at.