Hey zman, download that pic that you posted & see if it has the same issue as your original. I don't think it will.
In your screenshots, your affected images have the icons for exif data & embedded thumbnail, yet the version downloaded from imgur lacks both of those. Clearly imgur made some kind of changes to your pic, which means it's useless as a sample. (However, it does point toward where the problem might be.)
If the downloaded image doesn't have the problem, then try this: Open the original pic, click edit->metadata->remove exif thumbnail, then save it as a new image & see if the new image still has the issue. If not, then you know the problem lies in the embedded thumbnail.
btw, What program did you use to create the image in the first place?
Oh the feuhrer, oh the feuhrer, oh the feuhrer's nipples bonk!