Microsoft Surface Arc Touch Mouse Bluetooth appears to pair but doesn't actually connect or work

I'm trying to connect a Bluetooth mouse to a new Intel NUC with a fresh install of Ubuntu 16.04. I have installed blueman-manager 2.0.4. The device can be found (it comes up as 'Arc Touch Mouse SE') but when I try to pair it, most times it fails. Everyone once in a while Bluetooth Manager says it successfully pairs, but the mouse itself never recognizes the pairing (ie. it continues to alternate red/green blinking) and never starts to work.

Just to confirm that my bluetooth is working fine (and that I'm not a complete idiot) I was able to quickly pair some Turbine T+3rd Gen headphones. They work perfectly.

Not sure what other info I can provide to help you help me.

Thanks!
Craig