Some carriers also require your phone to be on their whitelist - for example AT&T.

And Verizon claims they don't do it that way, but we had a phone that worked on Verizon with an old SIM card until Verizon caught on, and then suddenly it wasn't compatible with their network and couldn't be used on Verizon.