The conversion process of an MP3 involves filtering and also an elaborate elimination process to cut out redundant and less important information which is within a sample....
MP3's compression method makes use of the phenomenon called
auditory masking together with some clever algorithims to help keep the information needed to re-create the file to a minimum. For more information on how the MP3 process achieves this read
Psychoacoustics.

.
For a simple example of how data can be lost or distorted check out the pic I made up below, illustrating the conversion process, showing the resultant wave created by the process of coding, and re-coding a "sample" of music:
* In the first waveform you can see that the MP3 file has certain points of data (green dots) that give the "road map" for the recreation of the sound sample. It's important to understand that the MP3 (player/coder/de-coder) program doesn't see the brown line joining the dots together... only the green dots, which help it re-form the sample.
* the second waveform shows the re-intergration of redundant data, so it can again become a WAV file for use in a CD player. Notice that the MP3 program simply provides the same sample numerous times (depicted by the green dots) to fill in the gaps, as it cannot see the slope of the waveform (depicted by the brown line) as it re-samples the data into the larger WAV file.
* the third waveform shows the re-sampling of the WAV file into the same format as the original MP3 file was.
* the last waveform shows the resultant sample which, even though it was sampled using the same bitrate as the original file, it has changed ever so slightly and therefore cannot be considered a perfect replica of the original MP3. This will continue until the MP3 process breaks the waveform down to a point which is simple enough to intergrate perfectly.... This waveform would look more like a bar graph than a music sample

.
Of course... the MP3 process is actually much more involved and complex than this, and the MP3 process actually attempts to simulate the interlinking line to some extent, but it's not perfect by any means...
:edit:
Your right in thinking that there is only so much data that the MP3 process can discard before there is none left that is irrellevant, for eg: cutting out under 20Hz, and over 16KHz would only have to be performed once.
It's the sampling process that creates the most flaws, as well as the process of removing masked sounds... What may have been considered an important peice of data in the first sampling process, amy be considered less important on the next re-sampling process simply because when the waveform was resampled the data produced was slightly different.