OK, so I've gone through enough how-to's online on jailbreaking and unlocking this iPhone. I've got to be doing something wrong. When I insert my new sim card, it still tells me that the sim is locked.
Currently, I am running 4.2.1, baseband 5.13.04, jailbroken via redsn0w, installed cydia 1.2.7.

I've tried:
Use the original 5.14.04 baseband that was on the phone, jailbreak and unlock (nope)
Upgrade to 6.15.00 baseband, jailbreak and unlock (nope)
Downgrade to 5.13.04 baseband, unlock (nope)
Restore to original factory settings (bricked it)
Restore with a custom IPSW found online, re-jailbreak and unlock via Cydia 1.2.7 (nope) <-this is where I am currently.

The phone was with Rogers (ATT in USA) but I am with another carrier in Canada (Koodo, uses Telus)

Anything else I should try? Help is much appreciated!