If personal identifiers were such a great idea, there would be no need for a legal mandate because consumers would be willing to buy a phone with one anyway.
I am not saying a mechanism like it is a bad idea, but legally forcing everybody with a phone to join a public database for their 'protection' will do more harm than good. The existence of the database means that tracking will have occur to keep track of active phones on the network. It tramples privacy, making it difficult for lawful citizens to maintain their anonymity unless they are willing to live under a rock.
A being a part of this should be a choice make by the user not the government.
Government wants to know and control everything about you. If a thief steals your phone, why are they going to care about some stupid identifier tempering law? Come on, how stupid do they think are are...
Like others have already noted, there are unique identifiers on phones, IMEI or the older (maybe still used?) ESN. Unless you have a way to re-write those, I can't imagine a stolen phone being useful. If I took a stolen phone into a Verizon store to get it 'activated', wouldn't they know right away it belongs to someone else, based on the IMEI number? Or do stolen smart phones just become someone's IPOD for just media playing, and never activate the phone?