I know this answer is for an issue that is just a little stale, but today, I discovered (on my Verizon iPhone 4) the entry in settings for Personal Hotspot was completely missing. I finally got into Settings<>General<>Network and also found it there. When I turned hotspot on there, the entry back in the place it dissappeared from came back.
Funny how stuff just works like voodoo sometimes.
Brian