Sembra che questo problema esista ancora sull'ultima versione di OS X (El Capitan, 10.11). Sono stato in grado di trovare questo nei miei registri di sistema:
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)"}})
Sembrerebbe che ci sia un qualche tipo di problema di connessione con i server di autorizzazione di Apple (di cui ha bisogno per convalidare le credenziali di iCloud). Tuttavia, ho ricevuto questo messaggio in un momento in cui il mio iPhone non presentava problemi di connettività (servizio completo per cellulari).
Archiviato un radar (23058238) con Apple. Aggiornerò questa risposta quando / se sentirò qualcosa.