I have had this same problem. My phone first started out just losing bluetooth connection here and there. It would lose connection while talking on the phone or when listening to music in my car or on headphones. Bluetooth would randomly turn itself off thru out the day while not connected to anything. It got to where it would not find anything just as you say.. I sent it back and they sent a new phone. Now its doing the same exact thing. My wife has a Moto X pure edition and its doing the same thing too. I really wish I knew how to fix it or they would send a phone that works.. I would even except a less phone or a different phone like the play. But it looks like it is a Moto problem.