Even after purging all k3b related packages and reinstalling, I do not have an MP3 option in the Filetype selectbox of the ripping dialog.
The problem still remains in Lenny Stable. I can confirm that KaudioCreator is able to use lame. So it I think the problem would be in the k3b package and how it determines where to pick up the encoder. MP3 is not listed k3b as an Encoder.