I received this error with a 75x75 png about 13.4 KB. I tried re-saving it from Photoshop as a high quality jpg, which made the file size go up to something like 35 KB, and I still received the error. For pngs, the only option Photoshop provided me with when saving it was None or Interlaced, and by default None is selected so that's what I always do. However, upon changing it to Interlaced, which made the file size go up to 15.0 KB, it uploaded successfully.
So if you're having this issue (since no one posted a solution) try an interlaced image I guess.