Was the Storm you tried unlocked? If not, then it wouldn't work. Also, the SIM in the Storm is for international use. It is not active unless the user calls the carrier (Bell or Telus in your case) and asks to provision the device for international use. That would explain why it wouldn't work in your Bold.
Normally you would be correct. But seeing how CDMA is typically used in North America and very rarely used in other countries, they've began making them GSM/GPRS capable to support those that travel outside of NA.
As for the exclusivity contracts, yes, they do exist. However, the Storm 9530 is exclusive to Verizon here in the US. However, people have purchased them, had them unlocked and use them on AT&T and T-Mobile.
Take a look here for some more info:
Unlocked Storm on AT&T or T-Mobile