Distortion occurs after indexing (256) and "export as"
So I guess you went to Image/Mode and changed it to Indexed?
I would not do that, because it greatly reduces the number of colours you can use, and causes those distortions as you noticed.
I usually just draw my skin in default RGB mode (full colour), then export to .bmp with the following settings:
This will create a 3MB skin, which I then use Bright to reduce to 1MB.
I'm not sure how Bright does it's magic, but to my eyes the resulting skin looks just like the 3MB one, without any colour loss!
(it's a good idea to back up the original 3MB skin so you can compare it with the 1MB)
By the way, that is a very nice skin you made