Fingers, I think that all you need to do is to install liblame0 (if that doesn't do it you can try also installing lame and liblame-dev). I know that rezound will work with mp3's for me...both opening and saving to them. You can install the lame library with apt-get if you have these sources in your list:

Code:
deb ftp://ftp.nerim.net/debian-marillat/ stable main
deb ftp://ftp.nerim.net/debian-marillat/ testing main
deb ftp://ftp.nerim.net/debian-marillat/ unstable main