As this also happens in rhythmbox I'll reject this bug for banshee...
You probably don't have avahi-daemon running, see bug #56426
** Changed in: banshee (Ubuntu)
Status: Unconfirmed => Rejected
--
Fails to load
https://launchpad.net/bugs/66037