Phone cannot connect to headset.

[Derbysquire]

I have a Sony xperia M5 and although both the headset and phone recognise each other the headset says it could'nt pair. The M5 saves the headset as paired device.
Anybody else? Thanks.