I have an iPhone 5 on Sprint and this happens all the time for me when trying to connect my iPad Mini Retina. I have to turn off hotspot, toggle airplane mode then turn on hotspot again and then on the iPad I have to go back into WiFi settings from any other section of settings for it to properly refresh the list and SOMETIMES my iPhone's hotspot shows up and is able to connect.
Pain in the ass, especially if I'm tethered via usb to my laptop and don't want to interrupt the connection. Once the iPad is connected it will typically lose that connection if the screen turns off, at which point I have to go through all those steps again to get it to reconnect.
iOS 7.1 on both devices and both are jailbroken, if that matters. POS Dell laptop that won't even find the wifi broadcast thus why I have to use the usb cord. I had a mid 2010 MBP and it never failed to find or connect to my phone.