I've just installed a brilliant little script called audio-convert that allows you to easily convert your audio files from one format to another. It supports most audio formats and best of all, it can be used as a Nautilus script - this makes it a breeze to convert a bunch of files, simply by highlighting them in the browser, right-clicking, selecting "Scripts", then "audio-convert". You are then prompted, by way of a nice Zenity interface, to specify what output format you wish to use, and how you'd like to populate the resulting files' metatags (artist/song info, etc.); you can either copy the source files' meta data, or manually enter it for each track as it's converted.
My desktop machine runs CentOS 5, so to install I simply downloaded the latest version from the site, checked the package's signature, and copied the audio-convert bash script contained within the archive to /usr/local/bin. I then created a symlink from /usr/local/bin/audio-convert to the ~/.gnome2/nautilus-scripts/ directory to allow access to the script through the context menu in Nautilus. That was all I needed to do - it is worth noting, however, that I did have all the relevant codecs already installed on my system, so if you're missing any, you'll need to get them before trying to use the script.
If you are a Debian or Ubuntu user, there is a deb package available on the site. This should allow for an even simpler install, but I have been unable to try this myself.
The only possible issue is that the MP3 files it produces seem to have a , which has caused problems for me in the past with certain devices and software. However, that said, I haven't experienced an issue with VBR MP3s for sometime and I know my iRiver H340 is compatible so it probably won't cause me too pain!