Well, I tried it with a lucario sprite and it actually worked, It will look as if it had 256 colors on the pallete preview thing but once you import it, it will just have the 16 colors in the pallete.
Do you get a message saying that it can't be imported? Did you add the transparent background?
You can try resizing it in paint or you can leave it as an 80x80, Index it, Fix it up and then resize the whole picture by going to Image -> Resize\Resample, once there go to the box where it says "Preserve Aspect Ratio" and disable it, then where it says "Set new size" and set them to "64 x 64". Now depending on how big the sprite is it might come out a bit pixelated.