I have the same device and it used to work fine. However, last Sunday, after some months of not using it, I tried to use it and it failed to connect in the same way as yours. As I didn't have time to investigate what was actually happening, I assumed that either the device was dead or my car's battery (which was really dead) was somehow preventing the connection. I said I would retry after changing the battery, but I forgot. I think I'd better try again one of these days. But now that you mention you have the same problem, I wonder if there was an update some time ago that broke something.