There was a landmark case about this same issue in 1936 concerning IBM punch cards.[1] IBM leased its machines to customers, and they also sold punch cards, which they argued were effectively part of the machine.
The pricing was an important component of their business model. IBM wanted to get the machines into skeptical customers' buildings before they had a chance to be shocked by the sticker price so that they could discover how useful computing really was. The per unit price of punch cards however increased with the volume of punch cards purchased—which arguably made sense if the customers got more value out of each punch card once they got rolling on how to use the machines.
Anyway, the US Supreme Court said that was too bad, and enjoined IBM from dictating that they must be the exclusive supplier for all punch cards as a condition of lease agreements.
The principle here seems like it should even be more clear. Are you leasing you phone, or promising to use purchase their service for 24 months at an agreed rate? You get to pay a hefty cancellation fee if you choose to cancel the service, but you are not required to return the phone.
IANAL, but it seems like the Clayton Act(1914)[2], was pretty clear about "tying", and it was affirmed by the Supreme Court. While that does not mean that cell phone providers need to help you unlock your phone (unless separate legislation affirms that responsibility), it seems both anti-competitive in spirit, and contrary to the doctrine of firs sale to legally prohibit customers from tinkering and developing their own capabilities and uses for their property.
[1] http://www.law.cornell.edu/supremecourt/text/298/131#writing...
[2] http://www.law.cornell.edu/uscode/text/15/14