I had some m4a encoded files I wanted in mp3 (don't judge me) so I cooked up a modified script from one found here, that does the trick.

# m4a2mp3
for i in *.m4a; do
  mplayer -vc null -vo null -ao pcm:fast "$i" -ao pcm:file="${i%.m4a}.wav"
for i in *.wav; do
  lame -h -V2 --vbr-new "$i" "$(i%.wav}.mp3"

rm *.wav

Update (06/19/07)
Just a quick note, you can use this to convert any supported audio file by replacing all the m4a with the correct extension. E.G. For flac replace m4a with fla. A nice little vim command for that would be :%s/m4a/fla/g
Update (03/18/08)
I posted a version to go from anything (that mplayer can play) to mp3 without editing the script. Check it out here.