I've rolled over my Amex cards several times, due to theft, loss, and the mag-stripe failing. Each time the transition has been absolutely seamless. And as far as the new number goes, only the last 4 digits will change. (In fact, it most likely will only be the last and 4th from last digits that change.) I've also been able to get a replacement card in a few hours. You can get a temporary card from almost any Amex agent, or you can get the real thing by going to an Amex service centre.