Why is my instant hotspot on Yosemite / iOS 8 inconsistent?
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.