This will require gstreamer0.10 installed. Here are the codecs I have on my system:
bfiller@ironhorse:~$ dpkg -l | grep gstreamer0.1
ii  gstreamer0.10-alsa:amd64                                    0.10.36-1.1ubuntu2                                  amd64        GStreamer plugin for ALSA
ii  gstreamer0.10-ffmpeg:amd64                                  0.10.13-5                                           amd64        FFmpeg plugin for GStreamer
ii  gstreamer0.10-fluendo-mp3:amd64                             0.10.23.debian-3                                    amd64        Fluendo mp3 decoder GStreamer 0.10 plugin
ii  gstreamer0.10-gconf:amd64                                   0.10.31-3+nmu1ubuntu5                               amd64        GStreamer plugin for getting the sink/source information from GConf
ii  gstreamer0.10-gnonlin                                       0.10.17-2ubuntu1                                    amd64        non-linear editing module for GStreamer
ii  gstreamer0.10-nice:amd64                                    0.1.4-1                                             amd64        ICE library (GStreamer 0.10 plugin)
ii  gstreamer0.10-plugins-bad:amd64                             0.10.23-7.2ubuntu1                                  amd64        GStreamer plugins from the "bad" set
ii  gstreamer0.10-plugins-bad-multiverse                        0.10.21-1ubuntu3                                    amd64        GStreamer plugins from the "bad" set (Multiverse Variant)
ii  gstreamer0.10-plugins-base:amd64                            0.10.36-1.1ubuntu2                                  amd64        GStreamer plugins from the "base" set
ii  gstreamer0.10-plugins-base-apps                             0.10.36-1.1ubuntu2                                  amd64        GStreamer helper programs from the "base" set
ii  gstreamer0.10-plugins-good:amd64                            0.10.31-3+nmu1ubuntu5                               amd64        GStreamer plugins from the "good" set
rc  gstreamer0.10-plugins-good:i386                             0.10.31-3ubuntu1                                    i386         GStreamer plugins from the "good" set
ii  gstreamer0.10-plugins-ugly:amd64                            0.10.19-2ubuntu5                                    amd64        GStreamer plugins from the "ugly" set
ii  gstreamer0.10-pulseaudio:amd64                              0.10.31-3+nmu1ubuntu5                               amd64        GStreamer plugin for PulseAudio
ii  gstreamer0.10-tools                                         0.10.36-1.2ubuntu3                                  amd64        Tools for use with GStreamer
ii  gstreamer0.10-x:amd64                                       0.10.36-1.1ubuntu2                                  amd64        GStreamer plugins for X11 and Pango
ii  libgstreamer0.10-0:amd64                                    0.10.36-1.2ubuntu3                                  amd64        Core GStreamer libraries and elements
ii  libgstreamer0.10-0:i386                                     0.10.36-1.2ubuntu3                                  i386         Core GStreamer libraries and elements
ii  libgstreamer0.10-dev                                        0.10.36-1.2ubuntu3                                  amd64        GStreamer core development files