I had this exact same problem and found this post...I didn't find the answer here, but as I was trying things mentioned above I figured out that Excel does not consider an image to be data so it does not sort it with the other information. I entered the number one (1) in every field where there was an image and then sorted ...IT WORKS!!! The number hidden behind the image...I tried a Print Preview and the numbers didn't show up...so this may be the fix.
Thanks to the reply by Gord Dibben on this thread, I got an answer I desperately wanted and have decided to register on this site for more such help I might need.
However, one correction to Dibben's reply - 'Move and Size with cell'need not be ON, 'Move but don't Size' is fine. The only other requirement seems to be that the picture visually lie completely within the cell boundaries. Which means that the cell should be resized to larger than the picture and the picture moved to lie completely within it.
If an object stretches vertically over several cells and one of those cells becomes higher (row height), the object will stretch to fit the new dimensions. That is if "move and size" is selected. Good for my application which does NOT involve sorting,