Here is how to fix that (from Ubuntu 12.04):
First, you will need your mouse ProductName and ID:
$ xinput list
...
Microsoft Bluetooth Notebook Mouse 5000 id=14 [slave pointer (2)]
...
Test a new sensitivity level (14=device id, 1.7=level - higher level lowers sensitivity):
$ xinput set-prop 14 "Device Accel Constant Deceleration" 1.7
Create a new xorg file for the new setting:
$ sudo gedit /usr/share/X11/xorg.conf.d/50-mymouse.conf
Containing the following:
Section "InputClass"
Identifier "Microsoft Mouse 5000" # Whatever you want
MatchProduct "Microsoft Bluetooth Notebook Mouse 5000" # Product name from xinput list
Option "ConstantDeceleration" "1.7" # The same value as xinput
EndSection
Setting now sticks after reboot.