On player skins the texture needs to be in an indexed format and not RGB, this can be achieved in photoshop by opening your image and going to Image -> Mode -> Indexed Colour... -> Possibly changing any settings and then hitting 'Okay', this should fix the problem, also make sure the texture is in a square, I usually use 1024x1024 for mine but 256x256 or 512x512 work too, I would advise against going above 1024x1024, it works but it often means a huge file size for the image. I would say even 1024x1024 is too big.