Solution: Go to the Edit menu, then down to Color Settings and Check "Ask When Pasting" (and maybe the others too).
I just installed Photoshop CS5 (on a Mac). It seems the default setting for the Color Settings (/Color Management Policies) throws a stick in the wheel for us pixel artists. If the image (the one in the clipboard) has a color profile different from PS's preferred one, it seems PS will dither the image to produce a "match". To make matters worse, PS isn't competent enough to collapse extremely similar colors with the "Image/Mode/Indexed Color..." conversion, so 255,64,255 and 255,63,255 won't be merged even though the other colors are extreme greens, yellows, etc. I just had an 8 color image (BBC micro palette) turn into 15 colors and Indexed Color refused to turn it back into 8.
When doing pixel art critique and paintovers, this can be a nuisance. I'm just putting this here so the world knows.