Tl;dr Block your card NOW, the new card is compromised.
Call the credit card company's 24/7 line and report the card compromised. Do that before reading on, to avoid fraudulent changes to the card.
Two things might have happened:
Scammer
It's not in fact the credit card company that contacted you prior, but scammers. If this is the case you need to report it to the credit card company asap, to avoid fraudulent charges. When they contacted you, did you reply to the info they had, or did you investigate and contact them using information you found elsewhere? If you investigated and used the info you found elsewhere it's probably not scammers that contacted you, if not this is a possible scenario.
Technical problem
The second option is that its' a technical problem that you got the exact same information. But if this is the case the persons that previously tried to do fraudulent charges still have access to your "new" card details, and you should regard this as a compromised card. Block it asap.
This happened to me once, I got 2 cards with identical information. My deduction was that the CVV will be the same if all other info is the same. I called the bank and they issued a new card, which had new info. But my case was different, since there were no fraudulent behaviour I didn't really worry.
When the cards are blocked
The most important thing is to get the cards blocked, no matter the cause of the problem. And use information found elsewhere to do that. When that's done you can relax. Now you can think about what to do next. I would ask for a new card, with all new information. And record the call, if you're allowed to do that according to applicable laws where you are.
In the future please be a bit careful of where you use your card, especially online. It's very easy for a dodgy company to save the card details and use for fraudulent purposes.