We did have my old speedo to experiment on, so we tried that before tackling the one on the bike.
I think you can do this without taking the speedometer off the bike.
[size=14]1.This is the back of the speedo.
2. Look for the small screw right in the middle - where the small circle meets the gear bracket. Unscrew this and remove.

3. Pull gear out of bracket.

4. Lubricate the gear. I think we used vasoline - or some lightweight grease.

5. Put back together and hope it's better![/size]
You can inspect the gear while it's out. If it's completely worn out that might be your problem. Don't know if you can just buy a new gear. We also found this site...
http://www.speedometer.com/ Don't have any experience with these guys, but they did answer our email with helpful info.
Good Luck!