Comment 24 for bug 267399

Using Kubuntu 9.04
I had the same problem.
I did as recommended above: Tick the checkboxes for Swap Byte Order and Write Wave Header in the popup.
then i tried #find . -name "*.[Ww][Aa][Vv]" -print -exec lame -h {} \;
and found, that lame was not installed on my system.
Using synaptic to install lame and
now I can use k3b to read a cd and convert it to mp3.

But I expect Kubuntu to do that out of the box.