Comment 2 for bug 493039

Abhijit,
Have you tried to install the following metapackage?
Ubuntu-restricted-extras.
It will install the package "gstreamer0.10-plugins-bad-multiverse", which gives the mp3 support.

You can also check this with the Configuration Editor (gconf-editor).
Go to system/gstreamer/0.10/audio/profiles/mp3
See that the "active" box is checked.