What size is your skin? I know for Pacific Fighters the 1024x1024 skin had to be 1Mb. When I make a skin I usually pass it trough "Bright" ( utility that transform the bitmap you save in Photoshop to a 1MB Bitmap that is accepted in the game.
When I do a skin I don't change the image from RGB to indexed in Phptpshop. I save it as bitmap, then pass it trough "bright". This utility save the colors while compresing the bitmap to 1MB. I do the same thing for AH.
Here is the link for Bright:
http://airwarfare.com/Sims/FB/fb_essential_files.htm#003
