A radio not having .mp3 capability in today’s market is completely unacceptable. So… go aftermarket.
I’ve been seeing kits for around $130 for the M5, and you can buy a great head unit from crutchfield for $150 to $200. And if you do go aftermarket, I highly recommend buying a head unit that has a USB port on front. I use that almost exclusively in my Camry – I just load a 2GB flash drive with.mp3s, .wmas, or non-DRM .aacs and just plug it in. It’ll shuffle within a folder, within the entire drive, you can add / remove music or other files from any computer, etc. When you take it out and put it back in (or turn the car back on), it'll start at the exact spot where it last turned off. But what I find myself using it most for is podcasts.
Each week I download a number of podcasts that I then listen to during my normal drives off of my flash drive, or when I exercise (off of my normal .mp3 player). There are a ton of free podcasts out there, the ones I get are NPR shows like This American Life, All Music Considered, and Car Talk, as well as the Clark Howard talk show (his podcasts are commercial free). The unit that I have in my ’95 Camry is the Sony GT410U but there are quite a few out there and there'll be even more in a few months once the '08 aftermarket car radios come out.
Don't spend money on CD changers - they are literally obsolete. For that matter, CD's are slowly becoming obsolete also. You'll be seeing more and more head units in the near future that do not play CDs.
I do not currently have a Mazda5, I was waiting to see what ’08 offered as well as waiting to see if Toyota and/or Honda were going to enter the 6-seater “microvan” market.