I had the same issue when I made a skin with GIMP. The exported PNG file was something like 16kb, and it was rejected as too big. I opened the file in GIMP and exported the image again as a PNG, but this time I set the compression level to 9. There was no loss in quality, and the resulting file was less than 5kb (maybe less than 2kb, but I don't remember). The compressed image was accepted. I don't know if Photoshop has anything like that, where you can adjust the compression level of a PNG file.