I recently discovered a handy audio conversion program that does not have much publicity (mostly because the program is written by a French person, and not covered in any English websites I could readily find).
The program is called XCFA (X Convert File Audio). It supports a wide range of conversion for input and output formats, and when using it under Ubuntu, it offers the option to (attempt to) automatically install any missing dependencies (such as support for FLAC, AAC, etc). It has additional features besides conversion, but I won't cover those here.
The general use is to start the program, go to the Files tab, and import the music you want to convert. It analyzes the input files and presents you with your options for conversion. (If you open a lot of files, it can be a little slow, but it's fast when opening just a few.) It's pretty straightforward and this is one of the nicer audio conversion tools I have used since dBpoweramp back in Windows. (I would not quite call this dBpoweramp for Linux, but it's the closest I have used in years, and certainly a viable alternative.)
Included is a picture of me using it to convert a bunch of my flac files to MP3s.
It appears to be available in Ubuntu in version 9.10 Karmic or later, which does not surprise me too much as the program is fairly new.