It was through a credit union, they had to give us a new number. We weren't traveling then it happened, I guess if we had really needed the card then we could have pushed it, but I don't know.
I wonder if credit unions are just slower. The same thing happened to me - our CU CC was stolen (the number, not the physical card) and it took a couple of weeks, I think, to get a new one.