RichMS is right about the normalizing and the file formats.
MP3Gain is far from perfect, but it'd the best and easiest I've found so far for MP3s. If the source material isn't compressed (as in signal compression, not as in ZIP), then yes, the normalization won't be as effective.
At least it's non-destructive (ie you can undo it back without messing up your mp3)