Is the color resolution of your desktop set to something greater than 256 colors? (I'll assume it is but the photo you posted appears to be using a pallette of less than 256 colors).
You might also try shutting down all other applications while photoshop is running to see if somehow other programs are causing a problem.
I can't think of anything else off the top of my head that could be causing the problem except for bad video drivers or buggy software. But the sample photo you linked to is clearly not a more than a 256 color image (it's completely dithered).