I am not sure if anyone else has come across this, but my client FedEx services in Magento stopped working altogether this week. After debugging I realised that the XML feed being sent to the FedEx server was timing out, I got a HTTP no response when debugging in NetBeans.
The URL for web services has changed. Modify /app/code/local/Mage/Usa/Model/Shipping/Carrier/FedEx.php around line 136, edit both the beta and production url from:
This seems to be the new URL that FedEx is using to receive requests. Hopefully this helps someone!