probably in Ubuntu at the time
[EDIT: Actually it was in Lenny: I've been here before and forgotten]. Now MP3 encoding requires LAME, which due to some patent issues, is not installed in most Linux distros by default. In Ubuntu, it's in the multiverse repository. A post on the Debian forum today reminded me of the issue- I checked and found I hadn't even installed SoundConverter on my Debian Squeeze. When I did install it, of course MP3 encoding wasn't enabled.
A quick Google search brought up instructions for enabling MP3 output in the major Linux distros. I added the debian-multimedia.org repository as instructed and installed the gstreamer0.10-lame package, after which MP3 output was enabled.
But that's not the end of the story. I noticed that after I had added the debian-multimedia.org repository, Synaptic was telling me there were updates available for several packages. At first I couldn't find any information about why this might be, and was wary about letting a third-party repository update packages, but then.... well, I think this will have to be another post.