Esta es la biblioteca que necesita k3b, para poder grabar CDs de Audio desde mp3.

Articulo Original: http://jfibergran.wordpress.com/2007/04/25/k3b-mp3-instalando-el/

En Ubuntu Feisty, K3b presenta un mensaje, en el que muestra el siguiente error:

Mp3 Audio Decoder plugin not found.
K3b could not load or find the Mp3 decoder plugin. This means that you will not be able to create Audio CDs from Mp3 files.Many Linux distributions do not include Mp3 support for legal reasons.
Solution: To enable Mp3 support, please install the MAD Mp3 decoding library as well as the K3b MAD Mp3 decoder plugin (the latter may already be installed but not functional due to the missing libmad).
Some distributions allow installation of Mp3 support via an online update tool (i.e. SuSE YOU).

Lo que pasa es que por tema de licencias, parece que han dejado de incluir un paquete en la distribución, la solución es bien sencilla, abrimos la consola y escribimos lo siguiente:

$ sudo apt-get install libk3b2-mp3

Esta es la biblioteca que necesita k3b, para poder grabar CDs de Audio desde mp3, sin embargo el mensaje hace referencia a dos bibliotecas, la otra es para poder reproducirlos, así que supongo que esta ya la tendrás instalada.