I've had bad experiences with wireless mice as well. Flagging battery life and conflicting frequencies convinced me to move back to a corded optical mouse. No problems.
I am looking at the new Razer Diamondback mouse they just put out. I was happy with their Boomslang and expect good things from this optical mouse they made.
http://www.razerzone.com/
As for your problem, I'd have to say, step backwards to start troubleshooting it. Go back to the MS Mouse you were using and see if the problem still occurs.