Add the following repo in /etc/apt/sources.list and do an update and install the latest Banshee, i assume you are using hardy
Code:
deb *ppa.launchpad.net/banshee-team/ubuntu hardy main
Also it might be good to delete .banshee folder from your home folder (i dont remember it might be in .gnome folder, just check it)
EDIT: Start BAnshee with banshee-1 from the terminal and use this How-To