I am sad to say that you’ve tried everything I would recommend trying. “Status -1” is a timeout, which can happen to any of the Android BLE related functions, so unfortunately that doesn’t narrow down the problem-hunting much.
Android BLE has been problematic since the beginning. If you’re using Android 4.3 or 4.4, I would look at upgrading, as later releases can be more stable. This varies by manufacturer though… the Android landscape is far less consistent than Apple.
One other thing that could help – on some Android phones the wifi and BLE do not co-exist nicely. Can you try again after turning off the wifi connection?
I’m sorry I don’t have any surefire answers on this issue, hope this helps