Well, you won't have much luck with compression programs (ie., winzip), because the data is already encoded. It might shrink it some, but I generally don't see much less than a 1 or 2% 'shrink.'
What you are going to have to do, then, is re-encode the .mp3 at a lower bitrate or with a different algorithm. I prefer using ogg-vorbis to .mp3 ... it gives a much higher quality product for the same size ... or a smaller size for the same quality product.
Your other option is, as I mentioned, to reencode the .mp3 at a lower bitrate, which will shrink the size of the file but also reduce the quality of the audio.
What encoding programs are you using? If you aren't, what OS are you using (so we can suggest some good programs for you to tinker with).