go to novaskin, open the skin there then click on "save". it will give you a link to download a skin that is exactly the same skin you opened there, but for some reason can be uploaded to minecraft.net
i know how to fix it! i downloaded a skin from skindex then edited it with photoshop. it then said "skins cannot be larger than 8kb" then go back into skindex, and go into the "editor" and click the "upload from computer" choose the Photoshop'ed image and then press download and that skin should work.