The scary thing is this happens a lot more often then you think.
Just google biggest security breaches. Sony made it to the top today. Before that Apr 11 2011 was the last record holder, not even a month ago.
And 9 days late in notififying, how about the Heartland disaster in 2009:
"In a statement Heartland said the breach occurred last year but that it found evidence of the intrusion last week and immediately notified law enforcement and credit card companies. The company handles 100 million transactions per month but does not know exactly how many unique cards or consumers that translates to, he said."
For as now it's still may have been compromised, nothing is certain.
The amount of information they could have gotten is readily available anyway. Name, address, phonebook. There are plenty of ways on the internet to find out someones date of birth and email address. Luckily the security code of your cc was not part of the vulnerable information, making any online purchases with the info impossible.
Credit card companies are well aware of the amount of security breaches. Hence we now have chip cards and verisign for online shopping and your transactions and card get blocked when there is suspicious activity. I once almost got stuck in a parking garage overseas because I had forgotten to notify my bank of my travel plans. If my wife had not gotten the call and convinced them it was me I would have been left with no card on my work trip. Before that my debit card got immediately blocked when I tried to get money out 3 times in a row at the same bank machine.
It's common sense not to use the same password for services that have information of you that you don't want to be shared. Especially not with sites that have a service to email you your password in case you forget it, meaning that your password is stored in plain text instead of hashed!
These things unfortunately happen all the time. Just be vigilant for phishing scams. Don't give out any personal info over the phone or email or fill out any info online before you are 100% certain who you are connected to. If they contact you then it's most likely not who they say they are.