Five months ago Apple removed the tethering functionality from factory unlocked iPhones with their 3.1.2 software update. This did upset quite a few customers and there were even official complaints in Europe about the issue. Unfortunately the complaints did not bear any fruit.
Finally gave up and jailbroke my iPhone. Wrote the step-by-step instructions below for future reference. If you decide to follow these, you are on your own.
- Factory unlocked iPhone 3GS
- iPhone OS version 3.1.2
- Download and run blackra1n
- Click rain from iPhone and install Cydia
- In Cydia app, add source: http://www.sinfuliphonerepo.com/
- Install "Enable Tethering for 3GS" in Cydia app from the above repository
- Reset the network settings
- Send operator settings IPCC file to phone. I used these the instructions at Hopeinen omena
- Restart the phone once more
- Go to operator menu and - voilá - you now have internet tethering.
Apple, please finally fix this. It is really embarrassing to force paying customers to go through the above procedure.