When I have the statistics window open on my Linux (Debian) box and I move the
mouse from the top left corner of my monitor to the top right corner, it counts
40 cm (which is what xdpyinfo says, too). However, when my colleagues do it on
their machine, it only counts around 16 cm which COULD correspond to the actual
movement of the mouse (not the pointer on the screen), which seems more correct.
Is there no way for you to get this information on a Linux system?

Your colleagues are running Windows? Workrave uses the 'dots per inch' as
reported by the X Server (on unix) or the OS (windows). So it should count the
distance on the screen, not on you mousepad. 

On my linux box, xdpyinfo reports:
dimensions:    1280x1024 pixels (433x347 millimeters)

This corresponds to a 21.8" monitor... Would be nice if this was correct :-)
I have no idea how to get the correct DPI.

What about changing the mouse movement measurement to measure the real move of
the mouse instead of the mouse pointer? This is IMHO, for this kind of program,
a more valuable information. The program could be calibrated to calculate the
real distance.

The Windows machines we've tried this on are both dual-head machines.. I didn't
really think about that, but it's probably significant.

Yes, the coolest thing would be to measure movement of the mouse, but it's not
really possible:
 * You can't just calibrate it, because it's going to be REALLY hard to
   take mouse acceleration into account
 * What about people who uses trackballs? mousepads? Touchscreens? etc.?