I have Logitech ball mouse and I use VooDoo pad - it kicks some serious ass.
I bought a "gaming" mouse pad - I forget which one it is, because I am not at home, but I have an optical mouse and when I'm playing games I do see a difference. The pad I got is 2 sided, one side is coarse and the other is smooth. It's pretty cool, I'll reply when I go home and look at what it is.
<Common Sense is a gift that some of us have returned.>