Have you used the Mobile Hotspot before with no problem? Assuming your going into settings > Personal Hotspot and toggling it to on correct? Did you change the Wi-Fi password to something other than the default? If not, I'd suggest doing that and then trying to connect again. From there you can connect via Wi-Fi, Bluetooth or USB per the instructions on that screen within the settings.
Frustrating for sure. Apple has been releasing updates to their software (quietly). Make sure you are updated to the latest iOS version (settings - general - software update). You need to have at least 50% battery life and be connected to a WiFi in order to do this (thanks Apple).
Not certain that will correct the issue, but this latest software fix from Apple has been fixing issues like this.