On ubuntu :

sudo apt-get install libk3b2-extracodecs

Many thanks to http://linuxappfinder.com/blog/howto_enable_mp3_support_for_k3b