I have exactly the same problem with my brand new Pebble 2 and both ASUS M180 (android 5.x) tablet and a Ulefone Power (Android 6.0) phablet
Luckily I could connect easily with an huawei Honor 5C (android 6.0)
From what I've seen the problem is device dependant, not android version dependant.
Except that @Tumi has announced the stuff worked with a Ulefone Power like mine.
@Tumi could you confirm ?
What could be the difference between your Ulefone Power and mine ?
Anyway, I suspect the app to be the problem rather than the firmware as I could not connect to the Ulefone and the Asus whether with the initial firmware installed on the watch or the one (4.3) I finally managed to install with the Honor 5C
Looking at the log (android log, use contact support to send the mail with a TarGZ to yourself) I've seen 2 messages which are maybe related to the connection problem
[BluetoothManager] Connecting to [ name = PEBBLE B6B5, address = 4F:34:2E:2E:5C:4F, transport = LE] failed: result = [result = NOT_AVAILABLE, reason = NO_PPOG_CONNECTION_HAS_ENCRYPTION, newAddress = null, failingGattStatus = 0, failingState = PAIRED]
and an increasingly dellayed connection timeout followed by an error about bluetooth LE method unavailable
12-22 10:25:10.089 11820 11820 D Pbl: [ConnectionStateManager/app] actionProcessBackoff init for [ name = PEBBLE B6B5, address = 4F:34:2E:2E:5C:4F, transport = LE] period = 1000 ms
12-22 10:25:10.097 11820 11820 I Pbl: [PebbleBluetoothAdapter] getLeState: error doing reflection
12-22 10:25:10.097 11820 11820 I Pbl: java.lang.NoSuchMethodException: getLeState 
Those errors where also available with the initial firmware so I suspect them to be the problem core... but I'm not sure as as always with java stuff you have to deal with a huge bunch of (mostly pointless) log lines ( and throwing null pointer exception errors is a major programming pattern in Java )
As everybody here I've no news from pebble support and I assume we won't have any as the developpers will probably be assigned to fitbit stuff. Too bad.
I'm going to investigate on genuine open source solutions to use this nice piece of hardware.
Does anyone has some links related to open source firmware for pebble ?