Well, if you follow the hack on MacAddict to add the developer tools into the PB, you can download the source for and encoder called LAME and compile it.
It's a command line encoder, but it produces EXCELLENT sounding MP3s. See http://www.r3mix.net for a good encoder comparison and details on the best configuration for LAME.
I did get this compiled into a binary under the PB, but I haven't tried encoding yet. I don't see why it should be a problem though.