Could this be a more widespread issue? I have had the following devices and they either refuse to operate the app or most of them even download it. The one device that did acted identical to this. In some cases it refused point blank to see the Bean, but will pick up unlisted Medical Encrypted Bluetooth Devices. One specific case is the Sphero BB8 unit. Works sometimes, most of the time ill be lucky to get it to see any BLE device.
*EVGA Tegra Note 7 (Org 4.0 | Laster 4.4 then I think 5.1 is the last OTA. It was a disater but the Bluetooth is the only consistent thing on it.)
*Nvidia Shield Portable (4.0 then 4.4 the finally 5.1. Talks of 6.0, but more than likely not going to happen)
*Motorola Photon Q (4.1) (Sometimes will see the Bean, but Play Store says no way.)
*Android X86 - 4.04 (Sees Beans, but PlayStore says no way)
On the PlayStore bit, some BLE applications are not disabled, and when downloaded work, so I know they have BLE. I don't understand the critera on how it decides, but most importantly to this thread......How Android allows the Higher levels of the OS (You) to control BLE signals and sending Pair/UnPair/Reboot/Resync commands. That got all messed up when I went from 4.4 to 5.1
However, my iPhone 5 picks up the Bean, those medical devices, and everything BLE without hesitation. The iPhone 5 almost always finds the Bean, but firmware updates almost always fail on CR2032s, so I went to a AA shield I made and it not only works, it increases the range and reliability of the unit.
Also a 6.3v 1000uF or Talium Capacitor will work wonders for finding the device.The iPhone app does fail when anything is above channel 9 of the 802.11B/G/N spec or if you have a CSR 4.0 BT device near with the "pirated" drivers. (usually cheaper china or amazon specials)
Here is something to try for the OP. It is not gospel, but it seemed to help me get some of my devices to find and flash it better.
Go to your bathroom and shut the door. Put the Bean in the sink and (No this is not a troll, do not touch the water, and make sure it isn't wet first.) put the phone near the faucet and attempt to flash again. Your creating an RF lightning rod for things that have 2 wireless cards in them such as the ChromeCast. These devices are the kind you have to WiFi to to configure and they give you a site survey to pick from.If your nervous about this and have a concrete basement, you can do the same thing with a basement waterpipe. Waterpies are "Earthed" grounds from the major grounding required for high voltage runs. Do not trust grounding in a house unless you can check it yourself. It just takes 1 Outlet twisting the Neutral to the Ground wire or putting them on the same screw terminal in the box to create a problem, then you have interference and everything that requires grounding in your house in a fight to the death.
If you want the science behind this, take a look at 802.11BGN standards and the terrible 2.4ghz spectrum. Also look up Faraday Cage (RF Cage), and RFID blocking wallets. All source in the some electrical science. It is a wonder that people aren't magnetic and confused when around all the wireless signals we have no control over. (RF interface can cause migraines if your sensitive, but oddly cures them?)
Also be careful about getting the back of the Bean shorted against metal. A piece of electrical tape will prevent this.
Spoiler: The microwave always wins!
Good luck, and I look forward to anything else anyone has on the OP's Issue, and/or mine, or how to prevent this.