Being in the UK I obviously don't have such Fed Ex issues to deal with.

Here in the UK we get offered a choice of options, carrier for which we pay a fee or free for which we don't.

Whereas free isn't going to be viable for long distance shipping it might be beneficial to offer an element of choice for shipping as Fed Ex-phobic customers may be put off placing an order in the first place?

Just a thought.