Tienes que instalar los paquetes id3lib y libmad. Puedes encontrarlos en
http://dag.wieers.com/home-made/apt/packages.php.
Una pregunta: ¿por qué no instalas el k3b "oficial" que viene en los CDs de Fedora 3? Así te evitas muchos problemas. Usa el programa system-config-packages y busca en la sección "Sonido y video".