The reason could be clipping. If the source CD is recorded at loud volume (= many sample values close to +/-32767) there are big chances that encoding-decoding causes clipping. This might lead to the results you describe. Try applying mp3gain to the files or use replaygain and a program capable of using replaygain information for decoding, e.g. foobar2000 (its Audio CD writer or Diskwriter + your favourite burning program).
What did you use to decode the mp3's?
ReplayGain and normalization are not the same thing. Normalizing a file will adjust the volume based on the raw data. However, not all frequencies sound as loud as each other at the same dB level. ReplayGain compensates for this and attempts to adjust the volume based on the apparent loudness. (I strongly suggest browsing the ReplayGain website.) For your purposes, this is the only difference, though it is an important one.In order to take advantage of ReplayGain, you'll need a tool that will convert back to wave, applying the ReplayGain info. Foobar2000 does this and is easy to use... highly recommended. My suggestion, and I'm sure many will agree, would be to store your music as MP3 (your requirement) and when you want to burn a music CD, convert to WAV using Foobar2000 and use those WAVs for the CD.
MP3Gain uses David Robinson's Replay Gain algorithm