For as long as I can remember, my Tesla app on Android wouldn't connect unless I saw the red T on launching the app. In almost all cases, I would see the red T every other time I tried to launch it. If I didn't see it, I'd back out of the app to try again and would see it and would connect.
With the update I just installed, I've tried 5 times and each time I've seen the red T and connected to my car in about the same amount of time I'm used to seeing.
Galaxy S5 on Marshmallow (6.0.1)