OK, here comes another "me too" with the payment issues. I tried 3 different cards from 3 different banks. Two of them are VISA and one of them is MasterCard. But nothing works.

I contacted my bank and credit card provider. They say that everything is OK at their end, but they haven't even received a connection attempt for the purchase. Now I have an open case about it with Nokia care. Let's hope something comes out of it.

But I believe, as some have already suggested, this could be the issues of using a foreign card with the localised Ovi Store. My cards are Finnish and I'm currently in Lithuania. I had the same issue with TomTom over here. Their payment system refused the transaction before it even tried to verify it with my credit card provider. It turned out that Lithuania is in the "black list" for foreign cards and they simply will not allow it.

UPDATE: I just tried to change the locale of my Ovi account from Lithuania to Finland and then try the purchase again, but it didn't help.