Having problems getting the module to return the right rate for shipping to certain countries.

We recently got an order from Reunion Island and initially the module returned a 0 rate for shipping. Customer was able to checkout with that and that is now making things a bit of a hassle to explain/work it out with him.

Can't seem to pinpoint what the problem is, as we're able to calculate shipping via Fedex's website just fine.

Does anyone have any idea what's wrong here? Has anyone have any problems shipping to Reunion Island?

One thing I did notice is that the Address Format (in the countries tab) is showing "0" whereas most others show 1 by default.