Many mp3 encoders cut off really high frequency stuff - somewhere between 16khz and 20khz depending on the encoder. Often this isn't changed by any of the quality settings, e.g. on lame it's still enabled on the "insane" preset without manually disabling it.
While that's on the very top-end of human hearing - most by middle age can't detect anything above 14-16khz, but it's certainly possible (especially for those younger) to have frequencies all the way up to 20khz as audible.
So it is possible for some people to hear a difference with some mp3 encoders, no matter the bitrate or quality settings.
And the psychoacoustic model is going to focus on the "average" listener, so it's perfectly possible that an lower bitrate encoding is transparent (IE: Completely indistinguishable) to one person, while another may be able to notice higher frequencies that have been cut off to provide more quality in the more noticeable parts of the spectrum. Or even the same person at different ages. This is completely physical difference, and no amount of training or harder listening would be able to bridge the gap.
And I find many of the higher frequencies that are hit by such things are often not particularly noticeable unless you're actively looking for them, being able to tell there's a difference and knowing what to specifically look far isn't the same as saying the recording is somehow less enjoyable due to quality differences.