Same problem here.

German Visa card (I am german and living there). I was able to buy Angry Birds level pack a few weeks ago with the same credit card.

And now they are rejecting the same card. The card is working, I am it for some other things (in different countrys mostly over the internet).

I wrote the OVI store support about it on Friday. Let's see what they answer.