When we had trouble like this before, I uploaded to flickr, then downloaded the medium size and was able to upload that image here.

I don't think it's the size. I've tried different methods: Adjusted size in photoshop, Uploaded to deviantART downloaded then tried to upload that, downsized the download from DA. I've tried different files. Changed the names. Bunch of stuff.