Strange that AerBabe - I had exactly the same problem a couple of days ago in work, and a colleague duly pointed out that because my mousemat had lines of different colour on it, it would cause it to jump around the screen. To be honest, I typed out my reply before I even read your post, and I had to delete it as the suggestions I was making - you had already tried! The only other possible excuse, apart from hardware failure - could be virus/spyware - but that seems unlikely. Try the mouse on another machine, and also try a re-install and let us know how you get on...
Cheers