You need to contact the seller and have them cancel their BIS account. If they won't do it, you can keep trying your carrier until some nice CSR will do it for you. You need to be patient and courteous, no ranting and raving as it isn't their fault it was registered to someone else.
And as an FYI, we are in no way connected with RIM. This is a private forum run and supported by an all volunteer, BB enthusiast user group.
I know this doesn't help, but in case you decide to buy another used BB, it has good information about buying used BBs and not just from eBay: Buying a BlackBerry off eBay - BlackBerryFAQ