Download the following two files and install them on your debian

http://www.las.ic.unicamp.br/pub/debian-marillat/pool/main/l/lame/liblame0_3.96.1-1_i386.deb
http://www.las.ic.unicamp.br/pub/debian-marillat/pool/main/g/gst-plugins0.8/gstreamer0.8-lame_0.8.10-0.1_i386.deb

Open a terminal and run
>gnome-audio-profiles-properties
>click edit on “CD Quality, Lossless”
>Gstreamer Pipeline - replace the word flacenc with lame
>Extension change flac to mp3

I am assuming like me you do not need flac - if you do just create a new one for mp3