Magento Fedex shipping from Belgium

I'm getting this dreaded message.

This shipping method is currently unavailable. If you would like to ship using this shipping method, please contact us.

As error messages go, this one is extremely unhelpful. I've seen many people facing the same issue, but most posts are from 2009 or 2010, and most people "sol开发者_开发问答ve it" by changing their American zip code (I'm from Belgium, so that can't be the case)

Does anyone know what I can do to get it working?

Seems like there is no available shipping for your quote. Do you use strict table rates ? Make sure everything is correctly set in your backend (Available shipping countries, postcodes, cart amounts etc...)