I´ve had the very same problem. Ended up calling and spent like 45min on hold because the call center agent was looking for a solution and even had to contact the supervisor and HQ in Dubai. In my case I was only able to use credit card payment. Paypal or other alternatives are not avail. for all countries.

Result was:
They did not know what was wrong. However, EK´s IT-system will automatically decline your credit card after 3 attempts for 24h. They ended up sending me a credit card verification slip, which I had to fill out and return to EK.