On Ubuntu 10.10, if you get an error message as the following when trying to create audio CD from mp3:
“Unable to handle the following files due to an unsupported format:
You may manually convert these audio files to wave using another application supporting the audio format and then add the wave files to the K3b project.”
Check if you have
libk3b6-extracodecs installed, if not just;
$ sudo apt-get install libk3b6-extracodecs
It fixed my problem.