There's the sticking point. It has never been tested in the U.S. if unlocking is truly lega. (Where I don't mean violating criminal law, but violating civil laws, such as copyright.)
The 'proof of legality' that has been bandied around is that the DMCA prohibits bypassing encryption routines, except for scholarly research; but every three years, the copyright office publishes a list of 'exceptions' to the DMCA. In the last cycle, they included cell phone unlocking. This list gets re-done every three years, and there is no guarantee that an exception from one cycle will be included in the next cycle. This means that unlocking a cell phone does not (currently) violate the DMCA, but nobody has ever tested to see if it violates ANOTHER law. For example, it might be perfectly legal to lock a user into one carrier at time of equipment purchase (aka, the iPhone's software license agreement.) In which case, the DMCA exception doesn't apply, and unlocking the iPhone may very well be "illegal", in that unlocking it violates the software license agreement included with the iPhone, completely separate from the DMCA.
Oh, and the next round of exceptions gets published in 2009. Meaning, if the cell phone unlock exception might very well get taken out before the first iPhones drop off their AT&T contracts. (Those who got month-to-month service, rejoice!) And, of course, no law has ever compelled a cell phone provider to unlock a phone. AT&T unlocking Motorola SLVRs is pure "goodwill" from AT&T, they don't have to do that at all.