MP3 Bit-rate converter

Bought a Fuji 40i which has the ability to playback mp3's. Problem is it can only play mp3 encoded at bit-rate between 96-128kbs, and all my mp3's are coded a lot higher than that. Is there a way to down-grade the bit-rate of mp3's, without resorting to converting to wav first.