DO NOT USE THE MAGIC WAND TOOL!!! It is only to be used for deleting picture backgrounds and it's not even that useful then. It deletes colors in the actual sprite image and causes distortion in the image as well. Whip can be useful but often poses the same threat to sprites at the wand. Background eraser is the best because unless you tell it to, it won't distort the image itself at all.
Do you have the tolerance turned to 0? This will make sure that the magic wand only selects the one exact specific color you asked it to. Also, don't forget to turn off anti-aliasing!
Also may want it either Contiguous or Global depending on what you're doing. Contiguous only selects that immediate cluster of pixels, while Global (or some name akin to that) selects all pixels of a certain color.

Just when you use stuff like PS for pixels, make sure that you have all of the anti-aliasing things off. ^^