Dani,
FedEx does not fully support the UK I am afraid, I got this reply from FedEx when I inquired about UK shipping:
I am sorry to inform you that at this time there are no Web Services available that provide domestic UK rating. We are trying to have this setup as soon as possible but we have no further information on it at this time. 
and my client would rather not use UPS because of service issues with them.


