Remove, deletes the program from your computer but leaves system-wide configuration files in place. So should you install it again, those will be there still with any adjustments you amde. Completely remove, deletes the program from your computer and also deletes these system-wide configuration files. So should you install it again, you will get a completely fresh set of system-wide configuration files.
Note that neither of these delete user preferences for Banshee from your home folder. I believe those are stored in the .config/banshee-1 folder (to display hidden folders like this, press Ctrl+H in your file manager).
Linux Mint 14 Nadia / 64-bit / Cinnamon