I've seen one of the Bluetooth guys from Google Glass say that it's perfectly normal in the industry to silently restart the Bluetooth stack before every connection attempt.

https://news.ycombinator.com/item?id=26647981

I guess Apple should adopt that too, since toggling Airplane mode on and off is the usual fix for issues with services layered on top of Bluetooth?