I had the same, last week.
Disconnect, removed bleutooth pairing
paired again..rebooted Phone...try again...
And again and again...took me 3 days, but suddenly the problem was gone.
Not sure what caused the problem or the fix.
But, I am once more a happy puppy with my Pebble time.
Oh...and I pair with Sony XPeria Z3, running Android 6.0.1
Never had problems connecting until last week..Coincidence ?