American Express Membership Rewards - My card number was stolen

I just went online to check my bill and saw that somebody had spent over $18k on home appliances over the course of two days in a country I recently visited in Europe. After looking at my activity when I was in this country, it seems like somebody in a restaurant or hotel took the numbers when I was paying my bill.

I called Amex and spoke with a lady who processed the fraud claim, but she never suggested that I change my card number. Isn't this something that they should do in such cases? What's to stop the same person using my card number again?

Yeah, you should definitely get a new card issued.

Not directly related to what happened to you, but see also:
http://www.flyertalk.com/forum/showthread.php?t=356064
...for another way people could get your card number.

This happened to me last June in Spain. I called Amtrak MasterCard immediately after 3 fraudulent charges appeared. MasterCard had already spotted this as potential fraudulent activity and was requesting that the person(s) using the credit card provide positive identification on future purchases. Apparently they had already attempted to use the card(s) 9 additional times by the time I called. There probably were multiple cards out there since one of the charges was for gasoline in Barcelona and the next charge was at a department store in Madrid 2 hours later. In any case, MasterCard cancelled the card immediately and issued a new number.