So since people still seem to come around here looking for an answer (I don't blame you, it's a good mouse), I decided to do some copy-pasting from my MX Anywhere 2 answer. Anyway, enjoy:
UPDATE FOR >15.10:
In my original answer I said that the problem would most likely be fixed when 15.10 comes around. While 15.10 does indeed have bluez 5, there is still some problem with pairing. Honestly, it was quite a while since I fixed this problem myself, but if I remember correctly, the MX Master (MX Anywhere 2) uses a PIN-less pairing method which isn't quite properly implemented yet in Ubuntu. Here are some commands which you can use as a quick fix:
hciconfig hci0 sspmode 1
hciconfig hci0 down
hciconfig hci0 up
If you're using another Bluetooth device than hci0, you obviously have to change that part of the commands, otherwise, they should be good to go.
ORIGINAL ANSWER (for < 15.10):
I had this problem a while back. Basically what's happening is that the MX Master requires Bluetooth Smart and Ubuntu ships with bluez (the Bluetooth driver) 4 which does not have support for Bluetooth Smart. Bluez 5, which adds support for Bluetooth Smart, is supposed to start shipping with 15.10, but for now, you'll have to install bluez 5 manually if you want to use it.
Just a heads up, if you want to have a stable system, DON'T DO THIS. First of all, this will break the built in Bluetooth control in the settings panel. This method that I'm about to describe adds a PPA too, which is supposed to be bad for your system when upgrading and stuff. Only do this if you know how to remove a PPA and revert to bluez 4 or if you just don't care and want to get it working. ;P
First, you need to add a PPA with bluez 5. I would recommend the bluez 5 PPA made by Austin since that's the one I have used before. Add it with this command:
sudo add-apt-repository ppa:vidplace7/bluez5
Then refresh apt-get:
sudo apt-get update
After that you can install bluez 5 with this command:
sudo apt-get install bluez
Now that you have bluez 5, you need a way of controlling Bluetooth since, as stated earlier, the built in control panel will not work anymore.
There are two ways which I have tried for this. If you want to have a GUI then Blueman is your best option. You can install it simply with:
sudo apt-get install blueman
This will install the Blueman Bluetooth interface which you can open for your app launcher. It should be straight forward to use and not require any in depth explanation.
The method I recommend however is to use the command line. I found this to be much more stable (worked on login screen while Blueman didn't) and actually surprisingly intuitive to use for being a command line.
The way it works is that you type bluetoothctl in to the command line where you'll now have a command interface to interact with Bluetooth devices. You can type help to get a list of commands and what they do. The command that you'll want to use first for pairing the MX Master is the scan command. If you type scan on, your computer will start searching for Bluetooth devices. While in this mode, put your MX Master in to pairing mode and wait for it to show up in the console. It will show up something like this:
[NEW] Device XX:XX:XX:XX:XX:XX MX Master
The "XX:XX:XX:XX:XX:XX" string is the MAC address of your MX Master. To pair it and connect it, type:
pair XX:XX:XX:XX:XX:XX
connect XX:XX:XX:XX:XX:XX
Make sure to change all the "XX:XX:XX:XX:XX:XX" to the MAC address you got when scanning.
And that should about do it. Hope it works for you!
Best Answer
Recently, I upgraded from trusty to xenial, via do-release-upgrade and had the same problem. After the upgrade completed, after the system booted, at the gdm login screen, I was unable to click anything with my mouse. I could move it around, and sometimes scroll, but I could not click anything. I had to navigate around with various key shortcuts like alt+tab and alt+f4
I tried a ps2 mouse, a wireless usb touchpad, and a different mouse. The mouse worked fine in another machine. Dmsg did not seem to show anything useful either. I tried all the obvious, like different usb ports to no avail. I reinstalled gnome-shell and gdm, purging configurations and even trying to update to the latest gnome 3.20. Nothing worked.
After lot of frustration, I installed gnome-session-flashback. That worked after switching to lightdm. The mouse would not click anything on either gdm or gnome3, but gnome2 worked fine. So next I installed kde-plasma, which worked. Than openbox, and mate, which also worked. Next I installed cinnamon, and the mouse worked, except I could not click anything on the status/menu bar down below. Everything else worked though, very odd. But if I understand correctly, cinnamon uses both gnome2 and gnome3 code, so I thought this information could be useful to someone trying to debug.
But I really just wanted my Gnome3 back. Finally I managed to fix this bug. I tried disabling my Nvidia proprietary drivers and switched over to Nouveau. After a reboot, gnome3 worked again. If you use any proprietary drivers, try disabling those. Hope that helps.
Update: After disabling nvidia drivers, and switching to Noveau, i than reinstalled the nvidia drivers, and everything worked fine. So that's worth a shot.