I'm using Ubuntu8.04. When songs switching, the background image generated by the "notification area icon plugin" seems to be unexpected.
Looks like a theme issue. If you use the Clearlooks theme with the default colors (be sure to reset them to be sure) does this still happen?
Either way, it's not a Banshee problem but will be a downstream one, either with your theme or with libnotify.