I have a Razer DeathAdder mouse and like in your case, the sensitivity/acceleration are too high even if I put them at the lowest level in the mouse preferences. So to solve this problem, I used the xinput command.

First, you will need your mouse ProductName and ID:

xinput list
...
 Razer Razer DeathAdder                     id=8    [slave  pointer  (2)]
...

Then you set the constant deceleration level that suits your needs with this command:

xinput set-prop 8 "Device Accel Constant Deceleration" 3
# 8 = DEVICE_ID
# 3 = LEVEL (factor) Higher = Slower.

To make the config persistent (and make it system wide), you will need to edit your xorg.conf (/etc/X11/xorg.conf).

Section "InputClass"
   Identifier      "Razer"                    # Whatever you want.
   MatchProduct    "Razer Razer DeathAdder"   # Product name from xinput list.
   Option          "ConstantDeceleration" "3" # The same value as xinput.
EndSection

Once you reboot, you should have the same result as the xinput command.

Let me know if it helps.

Ubuntu 17.04

Follow the instructions below, but change:

xinput set-prop 10 "Device Accel Constant Deceleration" 3

To:

xinput set-prop 10 "libinput Accel Speed" -0.4

Thank you @tambre. Not sure this is quite as ideal as the old setting, but it's pretty close.

xset m 3

That still works pretty darn well. Need to figure out how to save so this is the default on reboot.

Ubuntu 16.04

@JackTravis 's answer was incredibly helpful, but I think it's worth updating for 16.04 because the xorg.conf file has moved and been split into multiple files. Before writing this answer, I tried using xset and played around with the xinput settings for a while before deciding that JackTravis's xinput ConstantDeceleration 3 setting was the best one for both my Logitech M510 on my desktop and some older wired mouse on my laptop.

1. List Mice

$ xinput list
⎡ Virtual core pointer                      id=2    [master pointer  (3)]
⎜   ↳ Virtual core XTEST pointer                id=4    [slave  pointer  (2)]
⎜   ↳ Logitech M510                             id=10   [slave  pointer  (2)]
⎜   ↳ Synaptics Inc. Composite TouchPad / TrackPoint    id=13   [slave  pointer  (2)]
...

My mouse was the Logitech M510, id=10 so I'm going to use that in this example. You will need to replace that with whatever your mouse is called. Now, use xinput set-prop to try out various settings until your mouse moves exactly as you want it to. The 10 in the following corresponds to the id=10 for my mouse on my system. You'll probably have to change that.

2. Change Your Settings Temporarily

$ xinput set-prop 10 "Device Accel Constant Deceleration" 3

If you're curious what other settings affect your device try

$ xinput --list-props 10

To clear the settings after I had really messed them up, all I had to do was unplug and re-plug my mouse.

3. Save the New Setting Permanently

If you like ConstantDeceleration of 3, then you need to add an xorg.conf file the new Ubuntu 16.04 way: by adding a new file in /usr/share/X11/xorg.conf.d/ You will want to change Logitech M510 and logitech-m510 in the file name to match your mouse. I think the 60- at the beginning of the file name is the priority with which these files are loaded. The following one-line shell command is what I put in my machineSetup.sh file in Dropbox so that I can quickly customize a new machine exactly how I like it within minutes of a fresh install:

sudo sh -c "echo 'Section \"InputClass\"\n\
   Identifier      \"My awesome new mouse\"\n\
   MatchProduct    \"Logitech M510\"\n\
   Option          \"ConstantDeceleration\" \"3\"\n\
EndSection\n' > /usr/share/X11/xorg.conf.d/60-logitech-m510.conf"

OR, if you want to do it the GUI way, open an editor as root then paste and edit the following into /usr/share/X11/xorg.conf.d/60-<whatever>.conf

Section "InputClass"
   Identifier      "My Awesome Blue Mouse"
   MatchProduct    "Logitech M510"
   Option          "ConstantDeceleration" "3"
EndSection

4. Reboot

That's it. Just reboot and verify that the new settings took effect.

Late reply, but I think this is worth posting:

Since we're talking about gaming mouse here. Better is to turn off the mouse acceleration entirely (useful for FPS gamers etc.). Save up some CPU cycles by not using it to calculated any mouse acceleration and likely to be more accurate readings too (depend or the mouse hardware sensor has build-in extrapolation).

xinput set-prop <mousedevice_nr> "Device Accel Profile" -1

or

Section "InputClass"
   Identifier      "Razer"
   MatchProduct    "Razer DeathAdder"         # Product name from xinput list.
   Option          "AccelerationProfile" "-1" # Turn mouse accel off saving CPU cycles
EndSection

Source

A slight modification to Glen's answer, this works for my Logitech mouse and doubles "slowness" from 1 to 2.

Add to ~/.profile (as pointed out in comment) (or .bashrc but then you have to launch a terminal for the change to take place)

MOUSE_SLOWNESS=2
MOUSE_ID=`xinput list | grep Mouse | awk '{print $(NF-3)}' | cut -c4-5`
xinput set-prop $MOUSE_ID "Device Accel Constant Deceleration" $MOUSE_SLOWNESS

Sadly none of the answers worked 'enough' for my Ubuntu 18 Dell Wireless mouse. The speed was not slow enough.

This answer for a similar question helped me.

Use xinput list and get the device id. Refer top answer to do this properly.

Next do

xinput --set-prop 13(replace device id) "Coordinate Transformation Matrix" 0.2 0 0 0 0.2 0 0 0 1

Adjust the 0.2 above to any fraction as you want. Lower=Slower.

You can use the same technique as the top answer to make it permanent. Only replace "ConstantDeceleration" with "TransformationMatrix" and replace "3" with "0.2 0 0 0 0.2 0 0 0 1"

If you use the PS2 port the mouse movement is much slower for the same mouse resolution.

For your mouse try to use a USB to PS2 converter and put the mouse it the PS2 port.

Edit:

I have found the xorg.conf working solution:

Section "InputDevice"
    Identifier     "Mouse0"
    Driver         "mouse"
    Option         "Sensitivity" "0.2"
EndSection

Where a sensitivity of 1 is the default and the 0.2 one is decreasing it five times.

Read the manual for your mouse first before trying any of these other answers.

Razer brand mice have on the fly sensitivity features. For the DeathAdder that is mentioned in the accepted post, the one I use has 2 buttons on the top that controls sensitivity. If you make config changes first, you could one day have sensitivity that is too low because you unknowingly triggered the built in sensitivity features in the mouse.

I had just had this issue where I set the sensitivity as low as it would go and it was still too high, but it worked fine just days before. I had pressed the button to increase the sensitivity not knowing what they did, thinking I could use them as additional buttons for a game and ended up with very high mouse sensitivity. It's happened to me before, then would go back to normal and I never knew why, until just now.