First off you have the plug in dongle right? Second, how long or how many times are you giving your phone to connect? Sometimes it can take several attempts. Third, how close is your phone to the dongle? I read somewhere the closer the phone is to the dongle the better reception is and the faster the connection. I've tried that practice only once and it seemed to connect faster. Other wise I simply just kept trying till it connected. Key on, not started.
I use these types of apps on two totally different vehicles and connecting is clunky on both