We're a Cypriot company, so our transactions go through Cyprus. Unfortunately some banks block transactions from this country, but they shouldn't be able to deny you if you request that they make an exception in your case. They may try to convince you otherwise, but I don't believe they are allowed to deny such a request.

As kodeen mentioned, PayPal is a good workaround. If you experience issues using your credit card through PayPal, then the 100% waterproof solution is to use the "Add Funds" option, put some money on the PayPal account, and then use that money to make actual online purchases. This should allow you to bypass all and any bank-related problems and limitations.