k3b-mp3? Are you just burning mp3s - audio cds?
If so, k3b just uses the mad library (
http://www.underbit.com/products/mad/) to decode to wav then cdrecord I believe to burn to audio cd (cdrecord dev=/dev/cdrw speed=32 -audio *.wav or something like that).
There is a problem with 2.6.8 and burning. If you are using 2.6.8 (check with uname) either downgrade to 2.6.7 or updgrade 2.6.9 (which I believe has resolved the issue)