I'm assuming you have the new version of PSE and used that to save the files in the other formats. Unfortunately, that sounds like the common link.
Do you have any other image editing/viewing apps? Even iPhoto? I think you can still get free versions of GraphicConverter. My reasoning is try creating the different versions/formats with another app and see if any of those retail places can read those. You might even try PSE, again. Sure hope you can get that image restored!
BTW, don't use any non-keyboard characters in the file names, Windows is not terribly 'smart'.
Also no "\", "/", "?", ".", or even spaces! And make sure the name starts with the 26 letters of the alphabet, also.