I always have to startx twice for my mouse to work
I am using debian testing, a usb mouse, gnome. I was using xfce4, but was having the same problem. Only with gnome it's worse because gnome takes longer to start, and I have to rm /tmp/.X0-lock.
I boot up, and my mouse pointer is frozen. I ctrl-alt-f1, rm /tmp/.X0-lock, and startx; then my system comes up, and my mouse is fine.