You can try Blueman as @Shjim has said. Some bluetooth devices just don’t work as well as others. They can be working first time or not. Depends on the make and chip they use.
Edit: Always make sure it isn’t paired with something else. If you have other bluetooth devices around sometimes they automatically pair or connect without you realizing and then it won’t work on another device at the same time.