iPhone: Internet Tethering option is gone!?

If it happens to you, on the phone, navigate to help.BenM.at, follow the instruction to reinstall carrier profile.

This works 3G, 3GS, OS version 3.1 or up, no need to jail-break.