Credit card numbers are nation specific. The first numbers of the CC number indicate the country where the card originates from. While a french card might work perfectly well in real life, in some case it doesn't online.
I have a similar issue with my Dutch credit card, while I live in Belgium, so Belgian address, with a CC with a Dutch number (I do work in the Netherlands, hence the Dutch card). There is no way I can for example pay in Apple's App store, nor in iTunes. I am getting similar messages like you, when I try. Everywhere else in Belgium there is no issue when I pay. In this specific case, the only solution is to buy the iTunes vouchers in the supermarket.
I suspect that you are facing a similar issue. I guess it boils down to fraud protection. While in real life they can verify who you are (signature, pin code etc), online they have to trust you. Unfortunately, in many cases an online payment in one country, with a credit card from another country, where the delivery address isn't even in the same country usually is online fraud. Some vendors then simply block payments from cards originating from other countries. In my case a verification on my address to which the card is registered would proof my card to be legit, but I guess if even Apple doesn't want to do that, many other won't either.