I also just joined and received the same email on 5/1/12. It *did *include the CVV and it referenced an anti-virus purchase 10/28/2010. We have changed the card but it’s not with any of the banks previously mentioned.
At the least, it’s unnerving; and at worst, this casts a question on all internet transactions. 
This whole scenario is very confusing. Let’s get the obvious out of the way first though:
Yes, if you got that email, you need to cancel your credit card.
Please learn your lesson, and don’t buy crap from random unsolicited pop-ups.
That said, it’s a really confusing email. As suspicious as it admittedly looks, how can it possibly be a scam? What exactly is the plan here? Step 1: surreptitiously obtain victim’s credit card details. Step 2: email victim, tell him what you’ve got, and encourage him to contact his bank and law enforcement. What the hell?
This sounds to me like a second chance, follow-up scam, being perpetrated against previous victims of rogue security program infections, who paid money to have the fake infections removed.
The people who distribute fake security software are all in the former Soviet Union. Their business model has recently taken some major hits as payment processors have either been shut down, or stopped accepting payments made to these gangs. You can learn more about how Russian/FSU cybercrime gangs operate and run affiliate programs by following Brian Krebs on Twitter: https://twitter.com/#!/briankrebs - or by subscribing to his blog. He outs many of the people behind these scams.
The way the alleged informant got your contact info was via purchases you made through the affiliate network set-up for rogue AV and other fake software. Once you submitted your credit or (heaven forbid) debit card details and security code to them, along with your legal name, etc, they had the means of contacting you directly. Now that the fake AV business is declining (due to legal pressures), the merchants behind them are running follow-up scams to try to get more money out of their previous victims.
Note the last sentence from the scam email, which I pasted into the quote before my reply. The person is providing you with a link to a domain that was supposed to be under his/her control, to contact their “legal Department for compensation.” This is a 100% scam, being run by the very same people who scammed you out of a payment sometime in the past, for useless rogue anti-virus or defragmenting software.
As to the question about changing your credit card number, or ccv, that should be obvious, unless you have already had it changed for other reasons.
Contrary to what I have read in previous posts in this thread, gredine.com is a registered domain, meaning even if no web pages exist, its mail servers can be used for incoming and outgoing contacts in scams. When enough complaints are filed with their hosting company, the hosting gets canceled and off they go to sign up with another web host who provides POP3 and SMTP servers.
I invite you all to read some of the results from a Google search for gredine.com and Andre Shults. You will find many other anti-spam and anti-scam websites have outted these scammers.
Follow-up to my previous post concerning gredine.com. According to Domain Tools, the domain name has been suspended by its Registrar. However, as these matters go, the miscreants behind the scam will find a spam friendly Registrar and get the name working again. Then, their hosted email services will work again and the scam will continue.
Merely using IE doesn’t reinfect you. You are still very much infected. Starting up IE just makes the infection apparent.
You need to do some serious AV work on your computer. To continue using a computer with pretty bad malware like this is a very bad idea. The browser is not the issue (at this point).
You may need to wipe the disk and reinstall everything if it’s been running that long.
And change all your passwords to email, online accounts, etc.
The timing of this makes me wonder if it’s related to the most recent credit card hacking.
Is this a record date for number of new members? Holy cow and welcome!