Were all your phones from the telcos? Or did you buy some unlocked phones and try them on GSM networks?