Orange have now changed my plan, thethering is activated. Hopefully this is a good sign. It said somewhere that the plan would kick in when the phone was shipped and might start before I received it. I think.
Same with me on Orange. I now have tethering on my iPhone 4