If you successfully removed IT Policy, you no longer have any connection to the BES. This is because to successfully remove IT Policy, you must first wipe the device (Options --> Security Options --> General Settings --> (Menu) --> Wipe Handheld).
You can verify this by going to Options --> Advanced Options --> Service Books. All service books associated with your BES account start with "Desktop[".
More than likely your PIN is still registered to your old provider / phone number. You must get the PIN released by the old provider before it can be used on another existing or new BIS account.