Binary package hint: banshee
When I play a playlist of songs on Banshee (2.0) the applet in the top right corner (Ubuntu 11.04) will sometimes display the incorrect song rather than the song which is actually being played. When I press the "next track" or "previous track" buttons on either Banshee or my keyboard the applet will always show the correct song which is being played. However, if I leave a playlist to play through the songs the applet will display the previous song which was played and not the current one. It will always lag behind by one song until I manually change song which seems to correct it up until it automatically changes song again. This doesn't affect the notification pop-up which is always displayed correctly.
Banshee version: 2.0.0-2ubuntu1 (banshee)
Ubuntu version: Ubuntu 11.04
Please can you try to disabled in your banshee preferences the gapless and ppm options and then check if this issue persists?