Apparently this problem came up with previous versions of Rhythmbox, and a fix was supposedly found and applied, but I have Ubuntu 9.04 and the latest Rhythmbox release, and I still get the problem. What it is is that on every startup of Rhythmbox it asks to search for a missing ID3 tag demuxer plugin and then fails to find one. Previous discussions have stated that there is one inside one of the "good", "bad" or "ugly" gstreamer plugins accessible via Synaptic, and I have installed pretty well all of them (obtained using the keyword "gstreamer" in the Synaptic search box), and still the problem recurs.
The previous discussion to which I refer is here:
and there is some mention of "good", "bad" and "ugly" plugins here:
but it is two years old and rather inconclusive.