Fedex abrivations problem

Hi,
Shipping location is in Canada. We do have US based Fedex account.
And we would like to ship from Canada. To US and Canada.

If I setup our address as in Canada, as it should be, Fedex shipping does not work regardless where it is shipped to.
If I setup our address in US, shipping will work only for US delivery address.
If I setup our address in US shipping does not work to Canada.

Talked to Fedex support and they are saying that when Canadian address is either form or to address they receive full province name.
They expect province abbreviations, two letters, same as it is for US.

Please help.