Almost always this means the image dimensions didn't push it over the "sample" threshold, but the filesize did. So you see a reduced quality sample at the same dimensions.
Really, this message should show the lower ratio of filesize reduction and dimenional reduction.
Most of the time when that happens, the original image is a PNG. Not always, but usually. At least in my experience. And we all know what PNG does to filesize.
