I recently ran into a problem encoding some audio files under my Ubuntu Linux 8.10. There was no way I could bring the "Audio CD Extractor" or "Rhythmbox Music Player" to encode my CDs to mp3.
It took me some time to figure out what the problem was. There should be at least three packages installed, to be able to encode audio files to mp3:
My Ubuntu 8.10 did not have the last one installed. So I did a quick
"apt-get install gstreamer0.10-plugins-ugly-multiverse"
and the problem was solved.
The last thing I did was to create and activate an mp3 profile in the preferences dialog of the "Audio CD Creator"