Why is my instant hotspot on Yosemite / iOS 8 inconsistent? Sometimes, instant hotspot works in a split second. Sometimes, it works after 30 seconds, and other times, it just says "failed". In all cases, the state of the Mac running Yosemite or the iPhone is the same. To fix it, I have to restart one or both devices. What is the factor that is causing it not to work so I can always just turn it on without guessing which device to reboot? Is it something with bluetooth?
It appears this issue still exists on the latest version of OS X (El Capitan, 10.11). I was able to find this in my system logs:

10/9/15 5:25:03.213 PM   sharingd[679]   17:25:03.212 : Tethering: Request failed (id = 5D648B94-FFEB-44B2-BC8D-E116CA674465, duplicates = NO, error = Error Domain=com.apple.identityservices.error Code=23 "Timed out" UserInfo={NSLocalizedDescription=Timed out, NSUnderlyingError=0x7f9cfaece050 {Error Domain=com.apple.ids.idssenderrordomain Code=12 "(null)"}})

It would appear that there is some sort of connection issue with Apple's authorization servers (which it needs to validate the iCloud credentials). However, I received this at a time my iPhone had no connectivity issues (full cellular service).

Filed a radar (23058238) with Apple. I'll update this answer when/if I hear anything.