Answering my own question!
If you have another app using bluetooth it seems to get confused, especially if the other app is auto-connect. In my case it was Torque and it was essentially blocking the Soul EV Spy connection. Once I Quit the other app (no, I was technically not running it but it connected anyway) all is well. Note you can tell if Torque is active because it has a 1 next to the app icon on your desktop. To turn it off simply open the app and go to the settings, bottom left and choose Quit.
I am leaving my last post up and this one in case anyone else runs into the same issue.