Messages like "SIM card not supported", "SIM card locked", and "Invalid SIM" mean the phone is carrier-locked.
Even though the phone is locked, not the SIM card. It's the old trick providers use to make consumers assume their new provider is preventing them from joining (why wouldn't they want a new subscriber?), not their old provider preventing them from leaving (why wouldn't they stop you from leaving any way they can?)
You'll need to contact the provider which sold you the new phone (and which installed the lock) to get it removed. They'll still be able to lookup all the information they need to unlock it from your old account, it's on file forever, even if you've thrown away your receipts and the account is "closed". Indeed, the only critical piece of information they need is the IMEI (which is labelled in the phone's hardware and software, can be displayed on demand) and your ID (to prove you are the legit owner, not a thief).
But they might choose to be difficult, uninterested or reluctant in helping you out, they'll claim they can't do anything once the account is closed, they'll try to guilt you into staying, they'll imply some sort of betrayal, they'll perhaps offer "special one-time" plans/add-ons/discounts/deals (a bribe) if you stay with a new contract - they are very experienced and motivated with customer retention, you're not the first (and you won't be the last) subscriber they've lost.
If you don't want to deal with all this crap then you can be difficult in return - just remind them that CRTC wireless code requires them to unlock the device promptly at no charge, that even though it is still tolerated common practice it is also technically illegal for Canadian carriers to lock devices this way anyhow, and that you will either walk out of the store with an unlocked phone which works on other carriers or with a locked phone which supports your complaint to the CCTS.
