I am having exactly the same issue on Ubuntu Hardy an Banshee, even after upgrading Banshee from PPA to 1.4.2 . Have you managed to fix it?