I have just upgraded my system to Kubuntu 9.10 (Karmic). This has apparently broken Songbird. The fix I found on the web (removing libvisual-4.0-plugin, or so) does not work, since I do not have that package installed.
(songbird-bin:15641): GStreamer-WARNING **: Failed to load plugin '/usr/lib64/gstreamer-0.10/libgstlibvisual.so': /usr/lib64/gstreamer-0.10/libgstlibvisual.so: undefined symbol: gst_adapter_prev_timestamp (songbird-bin:15641): GStreamer-WARNING **: Failed to load plugin '/usr/lib64/gstreamer-0.10/libgstdv.so': /usr/lib64/gstreamer-0.10/libgstdv.so: undefined symbol: gst_tag_list_new_full ././songbird-bin: symbol lookup error: /usr/lib/python2.6/dist-packages/gst-0.10/gst/_gst.so: undefined symbol: gst_task_pool_get_type Could not initialize GStreamer: Error re-scanning registry , child terminated by signal
(I submitted this to their bug report system: http://community.bounceeverywhere.com/songbird/topics/gstreamer_problem_in_new_ubuntu_9_10)