Zolo Liberty android connection issue - connected (no audio)

I received my Zolo Liberties today and the first impression has been very good. At first I tried them with my MacBook and that was very easy and worked like a charm.
Then I tried my HTC One M8 and although it found a connection quickly it stated that there was only a phone audio connection possible. In the device options on my phone the media-audio box is checked but the media-audio is playing over the internal phone speakers. Is there any fix for a connectivity issue like that?

I succeeded once to pair the phone with the earphones and listen to media-audio, but it took me an hour to get it to work. That process involved resetting all network settings and turning off the wifi and more. So sadly that is not a viable option for the everyday use… I’d love to keep the earphones but for that to happen this issue needs to be fixed :S
Thanks in advance for any help!