The FedEx Dev Key is missing, incorrect or has not been switched to Production mode by FedEx.
Make sure the FedEx Dev Key field is not empty. Preferences > Shipping > Carrier Accounts.
Verify that it is the same as the one FedEx supplied you with.
Contact FedEx and verify they have switched it to Production mode.
Please refer to the chapter Ch. 016. Shipping (Setting up Carrier Accounts) of setting up the carrier account information for shipping methods.