Ok, this was fixed already a long time ago... closing the bug.
** Changed in: gst-plugins-ugly0.10 (Ubuntu)
Status: Confirmed => Fix Released
--
gstreamer0.10 refuses to play certain valid MP3s (not all, but some)
https://launchpad.net/bugs/42247