Personal Hotspot Not Connected Error

Ever since I updated my iPhone to iOS 5, I was unable to make my personal hotspot work. I set the Wi-Fi on and the personal hotspot on the settings but I’m still receiving a “Not Connected” Error. I certainly believe that this is not a problem with the connection since I can still connect using other device. Is there anyone out there who was having the same problem? How can I fit it?
