Hi
the deb way to go is
apt-get source k3b
apt-get build-dep k3b
apt-get install libmad0 libmad0-dev
cd k3b-0.11.23
dpkg-buildpackage -tc
dpkg -i ../k3b_0.11.23-0ubuntu1_i386.deb ../k3blibs_0.11.23-0ubuntu1_i386.deb
with this you get a k3b which has
/usr/share/apps/k3b/plugins/k3bmaddecoder.plugin
/usr/lib/kde3/libk3bmaddecoder.la
/usr/lib/kde3/libk3bmaddecoder.so
included. these are only included if during the compile the file mad.h is found. And as libmad0-dev is not required to compile k3b it is not downloaded during the "apt-get build-dep k3b" without the extra install you get a mp3 free k3b. (politcal reasons or just forgotten ?)
cu r13