Hi !

The libk3b2-mp3 package has been replaced in Ubuntu 8.04 by libk3b2-extracodecs.

So, from now, once K3b is installed, open a terminal and type :

sudo aptitude install libk3b2-extracodecs

Enjoy!