This happened on one of my Ubuntu machines where Igot some kind of segfault on line 21 from LAME at random while encoding MP3s (a second try is fine usually). I've read that it's best to compile it from source and that has solved most issues for people.
Here is my preferred configure line:
./configure --enable-mp3x --with-fileio=lame --enable-debug --with-vorbis
Even with that I got a different error this tim........