I had both of my credit card numbers got (potentially) nabbed at the same time around a month ago. New numbers for both.
But yeah, that totally sucks. I'm surprised they didn't go for trying to pay off a medical bill too. That seems to be a trend. Everyone I know who has had their credit card numbers stolen always mentions some dumbass trying to pay a medical bill with it.