Some MP3 encoders fail to create the proper file headers when encoding variable bit rate MP3 files. When that happens, the song length displayed will often be be incorrect when playing the song back. One of the ways this can be handled is by adding a Xing header to the MP3 file. One tool that's available on Linux to do this is vbrfix.
To install vbrfix in Ubuntu, first make sure that the universe repository is enabled in your software sources. Then you can install it through one of the graphical package managers, or from the command line with:
vbrfix is a command line tool. To use it, open a terminal window and navigate to the directory containing the files that you want to fix. Then, issue the command:
Where in-file.mp3 is the file to be fixed and out-file.mp3 is the fixed version of that file. You can also allow it to overwrite the old file with the newer, fixed version. Simply use the same file name for output as you use for input.
Now, if you would like to fix and overwrite all of the MP3 files in your working directory, you can use a loop like this. Note: this assumes your file extensions are all in lower case (.mp3).
I've never had a problem with vbrfix, but you might consider first copying your files to another directory make sure you don't screw up your original files.
To avoid needing a tool like this in the future, make sure to use an encoder that writes the Xing header. Gstreamer can do this if you include xingmux in the pipeline. Here's a script I wrote to batch convert audio files to MP3 using Gstreamer.