Solución:
Si bien no sé específicamente si se necesitarían opciones adicionales para solucionar el problema que menciona, ffmpeg es
una completa solución multiplataforma para grabar, convertir y transmitir audio y video.
Es la navaja suiza para audio y video. Volver a codificar sus archivos debería ser tan fácil como
$ ffmpeg -i oldfile.mp3 newfile.mp3
ffmpeg se encuentra en los repositorios de la mayoría de las distribuciones principales o se puede descargar de su sitio web.
No responde a la pregunta en su título, pero tal vez exista la posibilidad de arreglar los archivos sin volver a codificar. Por ejemplo, un problema común con longitudes incorrectas de archivos MP3 son los archivos con velocidad de bits variable que no están marcados correctamente como si tuvieran una velocidad de bits variable (y programas como rhythmbox los tratan como si tuvieran una velocidad de bits constante). La herramienta vbrfix puede reparar esos archivos. Otra herramienta útil para verificar el archivo MP3 es mp3check, también tiene opciones como --fix-headers que podría reparar los archivos (¡primero haga copias de seguridad de los archivos!).
Es posible hacerlo con lame y transferir las etiquetas id3 (las encontré aquí).
find . -type f -iname "*.mp3" | while read file
do
mv "$file" "${file}.old" &&
lame --mp3input -q 0 -b 192 --resample 44.1 "${file}.old" "$file" &&
id3cp "${file}.old" "$file"
done
Vea más scripts de conversión que he escrito aquí: https://github.com/sid-the-sloth/conversion-scripts