Just thought I'd chip in with the solution that worked for me.
I'm in the UK on O2 with an iPhone 4S (6.1.2) and the personal hotspot feature disappeared a few weeks ago after a seemingly random network settings reset on the phone (I was suddenly having to re-enter all previously stored WiFi network passwords!).
Because it seemed to be a reset that caused it, I was reluctant to try a reset again and have to again re-enter all the WiFi passwords, so I called O2 to see if it could be resolved at their end. They said no, but Apple Support could help and transferred me. Ha, that automated system wanted £25 so I said "No thanks"!
I instead bit the bullet and went to Settings->General->Mobile Data, scrolled down to reveal 'Mobile Data Network', selected that and scrolled right to the bottom of the Mobile Data settings to reveal the 'Reset Settings' button. Clicked that, confirmed that I was happy to "reset all network related settings to their original values" and hey presto, Peronal Hotspot was back under Settings->General->Mobile Data (scroll down for it) without me even having to reboot the phone!
The cool thing is, my WiFi connection remained (so the WiFi password is not wiped). I think this is therefore becuase this is a different reset from Settings->General->Reset->Reset Network Settings. That one will prompt for your passcode (at least mind does) and WILL wipe your WiFi passwords I'm sure. The correct one under Settings->General->Mobile Data->Mobile Data Network->Reset Settings does NOT ask for your passcode, mearly for the confirmation mentioned above.
For those in the US and other countries you may find that you need to substitue 'Mobile' with 'Cellular', but the process should be the same.
Give it a try!