"but WITH A BRAND NEW NUMBER. They said this is their policy."

It is not policy. They may tell you that, but I have had 3 replacemnnt AMEX cards in the last year (don't ask) and AMEX has always given me the same number. BUT, I had to state explicitly what I wanted. Be forcefull and don't back down if they pull that stunt. Far to many places have my account number for me to bother changing it just because I need a new card.