Hey, i had the same problem about 5 minutes ago, i figured out how to fix it, basically go to minecraftskin.net , click on a random skin, click edit, then click upload, choose your skin and click change. this will take you to minecraft.net with your skin already there, just click upload and boom, you're done!!
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.